Trong một cuộc hội nghị có $100$ đại biểu, trong đó mỗi người quen với ít nhất $67$ người khác. Chứng minh rằng trong hội nghị đó có ít nhất $4$ người quen với $3$ người còn lại.
Chứng minh rằng có ít nhất $4$ người quen với $3$ người còn lại.
Started By duaconcuachua98, 30-03-2013 - 19:50
#1
Posted 30-03-2013 - 19:50
#2
Posted 09-05-2013 - 20:00
Gọi A là một trong số 100 người đã cho,suy ra A quen ít nhất 67 người.Ta xét nhóm A và 67 người A quen,còn lại 32 người.Gọi B và C là 2 người A quen trong số 67 người trên.Ta có B,C quen ít nhất 66 người khác ngoài A,số người còn lại ngoài A,B,C là 97,suy ra B,C quen chung ít nhất 66.2-97=35người.Vậy giả sử 35 người quen chung của B,C ko nằm trong 65 người A quen còn lại thì số người quen chung của B,C tối đa là 32 người,vô lí,Vậy tồn tại ít nhất một người D là người quen chung của B,C và nằm trong số 67 người quen A.Nhóm A,B,C,D thỏa mãn yêu cầu bài toán$\Rightarrow Q.E.D$
1 user(s) are reading this topic
0 members, 1 guests, 0 anonymous users