giúp mình với minh dang gap. Mai dung roi. Cảm ơn trước

Question

Một câu lạc bộ có 42 thành viên sao cho trong 31 thành viên bất kì, luôn tồn tại ít nhất một cặp nam và nữ quen biết nhau. Chứng minh rằng có thể chọn ra được 12 cặp nam và nữ đôi một khác nhau có quen biết nhau từ câu lạc bộ.

Answer 1

Gọi k là số lớn nhất các cặp nam-nữ quen nhau trong CLB.
- Nếu k 12 thì ta có đpcm.
- Nếu k 11 thì gọi ( , ), 1,2,3,..., i i b g i k  là k cặp nam-nữ quen biết nhau. Khi đó trong CLB
còn lại 42 2  k người mà ta không thể chọn thêm cặp nam-nữ nào quen biết nhau từ họ.
Trong tập hợp này, ta bỏ đi 11 k người nào đó và chọn ra một tập hợp S gồm 31 k người còn
lại. Ta thêm k nam đã chọn ra trong bộ k đôi quen biết nhau lúc nãy vào tập S gồm 31 k người
này để được tập gồm 31 người.
Theo giả thiết thì trong tập 31 người xây dựng theo cách đó, tồn tại một nam trong k người thêm
vào, giả sử là 1
b quen với một nữ trong S.
Khi đó, rõ ràng 1
g không được quen người nào trong S vì nếu không thì ta đổi cách ghép 4
người này lại thì k sẽ tăng lên 1, mâu thuẫn với cách chọn k lớn nhất.
Tiếp tục quá trình này thì cả k nam thêm vào đều có quen với một nữ trong S và cả k nữ đều
không quen với nam nào trong S.
Khi đó, ta thêm k nữ vào S thì được 31 người mà không có cặp nam nữ nào quen nhau, mâu
thuẫn. Ta có đpcm.