Question

Trong phòng có 100 người,mỗi người quen ít nhất 67 người khác. chứng minh rằng chắc chắn tìm được 4 người mà 2 người bất kì trong số đó quen nhau

Answer 1

Xét là 1 người bất kỳ trong phòng

\(\Rightarrow\) quen ít nhất $67$ người
Nếu ta mời những người không quen ra ngoài thì số người ra nhiều nhất là $32$
Trong phòng còn lại $68$ người. \(\Rightarrow\)gọi $B$ là 1 người quen $A$ \(\Rightarrow\) có nhiều nhất $32$ người B không quen trong phòng
\(\Rightarrow\) số nguời còn lại là $34$ \(\Rightarrow\)gọi $C$ là 1 người quen $A$ và $B$ \(\Rightarrow\) $C$ không quen nhiều nhất $32$ người trong phòng
\(\Rightarrow\)trong phòng còn lại $4$ người \(\Rightarrow\)ngoài $A,B,C$ còn 1 người giả sử là ,khi đó $A,B,C,D$ đôi 1 quen nhau(đpcm)