Question

[uyen to]

Có 3 trường học , mỗi trường có n hs . Mỗi 1 hs quen ít nhất n+1 hs từ 2 trường khác . Chứng minh rằng có thể chọn ra tùe mỗi trường 1 bn sao cho 3 hs đc chọn đôi 1 quen nhau

Answer 1

[Trần Tuyết Như]

Gọi A là hs có nhiều bạn quen nhất ở 1 trường khác.gọi số bạn này là k.

giả sử:A ở trường 1 và những bạn quen A là B₁, B₂..., B_k ở trường 2.Ta thấy có:k lớn hơn hoặc bằng (n + 1) / 2 

Vì có ít nhất hs C ở trường 3 quen với A.giả sử C ko quen với B, ta có C quen với nhiều nhất n-k hs ở trường 2. suy ra C quen với ít nhất (n+1)-(n-k)=k+1 hs ở trường 1.

điều này mâu thuẫn với cách chọn A

Vậy C phải quen với 1 bạn nào đó

Ta có:A,B,C là 3 hs đôi một quen nhau

Answer 2

[Nguyễn Đình Dũng]

Gọi A là hs có nhiều bạn quen nhất ở 1 trường khác.gọi số bạn này là k.

giả sử:A ở trường 1 và những bạn quen A là $B_1$B1,$B_2$B2;...;$B_k$Bk ở trường 2.Ta thấy có:k lớn hơn hoặc bằng $\frac{n+1}{2}$n+12 

Vì có ít nhất hs C ở trường 3 quen với A.giả sử C ko quen với B, ta có C quen với nhiều nhất n-k hs ở trường 2. suy ra C quen với ít nhất (n+1)-(n-k)=k+1 hs ở trường 1.

điều này mâu thuẫn với cách chọn A

Vậy C phải quen với 1 bạn nào đó

Ta có:A,B,C là 3 hs đôi một quen nhau