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.
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)
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.
Chọn A là một học sinh trong hội nghị mời vào bàn. A có 50 người quen.
Chọn B và C là hai bạn không quen nhau trong nhóm này.
Nếu không thể chọn được B và C thì tất cả 50 người trong nhóm quen A đều quen nhau. Khi đó có thể lấy ba bạn bất kỳ xếp vào bàn với A, thỏa mãn điều kiện bài toán.
Trường hợp chọn được B và C, khi đó hội nghị có A, B quen A, C quen A ngồi ở bàn và 97 người khác. B còn 49 người quen khác A, C còn 49 người quen khác A, tổng cộng là 98>97. Như vậy B và C ít nhất có 1 người quen chung. Chọn D là một trong số người quen chung của B và C mời vào bàn. Ta có A,B,D,C thỏa mãn điều kiện bài toán.
Do có 6 người bất kỳ nên ta đặt tên 6 người đó là A; B; C; D; E; F ứng với 6 điểm A; B; C; D; E; F như hình vẽ:
Nếu hai người quen nhau thì ta nối họ bới một đoạn thẳng màu đỏ.
Nếu hai người không quen nhau thì ta nối họ bởi một đoạn thẳng mầu đen.
Dễ thấy từ A có 5 đoạn thẳng AB; AC; AD; AE; AF. Mỗi đoạn thẳng này được vẽ bằng một trong hai màu đen và đỏ tất nhiên phải có 3 đoạn cùng được vẽ bằng một màu.
Không mất tính tổng quát, ta giả sử có 3 đoạn: AB; AD; và AE cùng được vẽ bằng một màu đỏ ( Xem hình vẽ).
Xét tam giác EBD có ba cạnh EB; BD; DE. Nếu cả ba cạnh này cùng được vẽ bằng một màu đen thì Người E, người B và người D không quen biết nhau ( ĐPCM). Nếu ba cạnh của tam giác EBD không cùng mầu thì sẽ có ít nhất một cạnh màu đỏ (Vì mỗi cạnh được vẽ bằng một trong hai màu đỏ hoặc đen). Không mất tính tổng quát, ta giả sử cạnh BD màu đỏ. Khi đó tam giác ABD có 3 cạnh màu đỏ nghĩa là Người A, người B và người D quen nhau ( Điều phải chứng minh).
Nếu 3 đoạn: AB; AD; và AE cùng được vẽ bằng một màu đen ta vẫn xét tam giácEBD có ba cạnh EB; BD; DE. Nếu cả ba cạnh của tam giác EBD cùng mầu đỏ thi 3 người E; B; D quen nhau. Nếu 3 cạnh của tam giác EBD không cùng mầu thì sẽ có ít nhất một cạnh màu đen (Vì mỗi cạnh được vẽ bằng một trong hai màu đỏ hoặc đen). Không mất tính tổng quát, ta giả sử cạnh BD màu đen. Khi đó tam giác ABD có 3 cạnh màu đen nghĩa là Người A, người B và người D không hề quen biết nhau ( Điều phải chúng minh).
Do trong phòng có 100 người, mỗi người quen it nhất 67 người còn lại nên số người mà người đó không quen nhiều nhất là:
100-67-1= 32( người)
Ta giả sử 1 người bất kỳ trong 100 người đó là A. Nếu ta loại những người mà A không quen ra khỏi phòng thì trong phòng sẽ còn ít nhất 68 người( trong đó có A).
Ta lại giả sử 1 trong 68 người còn lại trong phòng( khác A) là B. Nếu ta loại đi những người mà B không quen ra khỏi phòng thì trong phòng sẽ còn ít nhất 68-32=36( người) trong đó có A và B.
............................. 36......................................(khác A,B) là C.............................................C................................................
.....................................36-32=4( người) trong đó có A,B và C.
Trong 4 người còn lại ta giả sử người khác A,B,C là D thì khi đó trong phòng có 4 người: A,B,C và D suy ra A,B,C,D đôi một quen nhau. Do đó tìm được 4 người mà 2 người bất kì trong số đó đều 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