Bài 5. ÔN TẬP CUỐI NĂM

Bạn chưa đăng nhập. Vui lòng đăng nhập để hỏi bài
Lina Janary

có 1 nhóm gồm 10 người tham gia 1 bữa tiệc.trong đó 1 người bất kì đều quen với ít nhất 5 người trong nhóm.hỏi có thể chọn ra 4 người ngồi vào 1 bàn sao cho mỗi người đều quen với 2 người ngồi bên cạnh hay không?

GẤP!!!

CÓ GIẢI THÍCH!!!

Akai Haruma
30 tháng 7 2020 lúc 23:16

Lời giải:

Bàn ở đây là bàn tròn.

Câu trả lời là có.

Ta cho người $a_1$ vào bàn. Giả sử người $a_1$ quen với người $a_2$ và $a_3$. Ta xếp $a_2,a_3$ ngồi 2 phía bên cạnh $a_1$

Giờ ta cần chỉ ra là tồn tại 1 người $\neq a_1$ mà cả $a_2,a_3$ đều quen để xếp vào bàn (giữa $a_2,a_3$) là được.

Thật vậy. Giả sử không tồn tại người quen chung nào giữa $a_2,a_3$ ngoài $a_1$

Khi đó, vì mỗi người quen với ít nhất $5$ người nên ngoài $a_1$ thì $a_2$ quen thêm ít nhất 4 người nữa là $a_4, a_5,a_6,a_7$.

Khi đó $a_3$ chỉ có thể quen $a_1,a_8,a_9,a_{10}$ (trái với giả thiết mỗi người quen với ít nhất 5 người)

Do đó tồn tại ít nhất 1 người quen giữa $a_2,a_3$ ngoài $a_1$. Xếp người đó vào chỗ thì ta được cách xếp thỏa mãn đề.


Các câu hỏi tương tự
chenchujian92
Xem chi tiết
Tuan Kiet Do
Xem chi tiết
Như Quỳnh
Xem chi tiết
QSDFGHJK
Xem chi tiết
hằng hồ thị hằng
Xem chi tiết
Blockman Go
Xem chi tiết
tiên lê
Xem chi tiết
Lê Ngọc Đăng Linh
Xem chi tiết
Egoo
Xem chi tiết