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 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)
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
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.
Trong một hoạt động ngoại khóa có 20 giáo viên và 80 học sinh đến từ nhiều nơi tham gia. Biết rằng mỗi giáo viên quen với ít nhất 65 người và mỗi học sinh quen với tối đa 12 người (Quan hệ quen được xem là có tính 2 chiều: Người A quen người B thì người B cũng quen người A). Ban tổ chức xếp họ thành 41 nhóm. Hỏi ban tổ chức có thể xếp sao cho nhóm nào cũng có 2 người quen nhau không? Vì sao?
Gọi Ua,U,Uc lần lượt là số dân trong các TP A,B,C.
Uab,Uac,Ubc và Uabc lần lượt tương ứng với số dân của TP A và B; A và C; B và C; A,B,C quen nhau. Ta có sơ đồ:
Ua Ub Uc Uab Uac Ubc 6000
Số dân của Tp A ko có người quen trong các TP B và C là: Ua-Uab- (Uac-Uabc)
......................B.............................................. A và C.... Ub-Uab-( Ubc-Uabc)
......................C..............................................B và A..... Uc--Uac-( Ubc- Uabc)
Tổng số dân của 3 TP ko có người quen trong các TP còn lại là:
Ua+ub+uc- 2Uab- 2Uac- 2Ubc+ 3Uabc = ( Ua- 2Ubc) + (uB- 2uAB) +(uC- 2uCA) + 3Uabc
\(\ge\)2000 \(\ge\)1 \(\ge\)1 \(\ge\)0
Vậy số người ko có người quen trong các TP a,b,c ít nhất là: 2000+1+1= 2002
áp dụng tính châts sơn tùng vẽ nên thôi thì có đpcm