Chủ đề này có 1 trả lời

[chuyentoan]

Có $n$ người, biết rằng:
(a) Trong ba người bất kỳ thì có hai người quen người còn lại.
(b) Trong bốn người bất kỳ thì có hai người không quen những người còn lại.
Tìm giá trị lớn nhất của $n$.
Ở đây ta giả sử rằng, nếu $A$ quen $B$ thì $B$ quen $A$.

Bài viết đã được chỉnh sửa nội dung bởi dark templar: 06-04-2013 - 16:23

[LNH]

Có $n$ người, biết rằng:
(a) Trong ba người bất kỳ thì có hai người quen người còn lại.
(b) Trong bốn người bất kỳ thì có hai người không quen những người còn lại.
Tìm giá trị lớn nhất của $n$.
Ở đây ta giả sử rằng, nếu $A$ quen $B$ thì $B$ quen $A$.

Ta sẽ sử dụng lí thuyết đồ thị để giải quyết bài toán này

Xét đồ thị đầy đủ có $n$ đỉnh, mỗi đỉnh tương ứng với 1 người

Ta tô màu đỏ cho mối quan hệ quen nhau, màu xanh cho mối quan hệ không quen nhau

Với $n=8$ thì dễ thấy tồn tại cách xây dựng thoả mãn

Xét $n>8$

Gs tồn tại một người $A$ nào đó quen với $6$ người

Khi đó theo định lí Ramsey thì tồn tại một tam giác được tô cùng màu, dĩ nhiên tam giác đó có màu đỏ

Kết hợp với $A$ thì tồn tại đồ thị đầy đủ gồm 4 đỉnh mà các cạnh được tô màu đỏ, vô lí

Vậy số người quen của $A$ nhỏ hơn hoặc bằng 5

Suy ra số người không quen $A$ lớn hơn hoặc bằng 4

Theo đk (a) dễ dàng suy ra 4 người này đôi một quen nhau, vô lí vì trái với đk (b)

Từ đó suy ra GTLN của $n$ là $n=8$