Hãy nhập câu hỏi của bạn vào đây, nếu là tài khoản VIP, bạn sẽ được ưu tiên trả lời.
Lời giải:
Số người quen của 1 người có thể chạy từ $0$ đến $n-1$ người.
Tuy nhiên, nếu 1 người quen 0 người thì sẽ không có ai trong số những người còn lại quen $n-1$ người và ngược lại, nếu 1 người quen $n-1$ người thì sẽ không có ai trong số những người còn lại quen $0$ người.
Tức là, Số người quen của 1 người trong nhóm $n$ người đó có thể chạy từ $0$ đến $n-2$, hoặc từ $1$ đến $n-1$
Coi đây như những chiếc lồng thỏ, thì có $n-1$ lồng.
Có $n$ người.
Theo nguyên lý Dirichlet, tồn tại $[\frac{n}{n-1}]+1=2$ người có số người quen giống nhau.
Ta có đpcm.
Xét A là 1 người bất kỳ trong phòng
\(\Rightarrow\)A quen ít nhất người
Nếu ta mời những người không quen A ra ngoài thì số người ra nhiều nhất là
Trong phòng còn lại người. \(\Rightarrow\)gọi là 1 người quen \(\Rightarrow\) có nhiều nhất người B không quen trong phòng
\(\Rightarrow\) số nguời còn lại là \(\Rightarrow\)gọi là 1 người quen và \(\Rightarrow\) không quen nhiều nhất 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à D,khi đó A,B,C,D đôi 1 quen nhau(đpcm)
trong phòng có 5 người thì số người quen của mỗi người có thể quen từ 0 đến 4 người
mà không thể xuất hiện 1 người qune 0 người và 1 người quen 4 người được
thế nên số người quen của 1 người chỉ là 4 trong 5 giá trị
nên theo nguyên lí dirichlet thì tông tại 2 người có cùng số người quen.
Tổng quát bài toán, trong n người bất kỳ luôn tồn tại hai người có cùng số người quen
