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
K
Khách
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.
Những câu hỏi liên quan
LD
3 tháng 11 2016
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)
PA
26 tháng 9 2022
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.
Xét A là 1 người bất kỳ trong phòng
\(\Rightarrow\)A quen ít nhất 67 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à 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 44 người \(\Rightarrow\)ngoài A,B,CA,B,C còn 1 người giả sử là D,khi đó A,B,C,DA,B,C,D đôi 1 quen nhau(đpcm)