Question

_{Có 10 bạn đi dạo phố bằng 5 xe máy. Biết rằng trong 10 bạn này cứ bất kì 3 người nào cũng có 1 người quen với 2 người kia.}

_{Chứng minh rằng có thể xếp 10 bạn đó đi dạo phố bằng 5 xe máy, mỗi xe đi 2 người quen nhau.}

Answer 1

Do số cách chia thành 4 nhóm là hữu hạn  nên ta có thể giả sử cách chia F gồm 4 cặp: (Ai,Bi)(Ai,Bi) là cách chia có nhiều cặp quen nhau nhất.
Giả sử trong cách chia F vẫn tồn tại một cặp không quen nhau là (A1,B1)
Khi đó trong nhóm 3 người gồm: A2,A1,B1 thìA2 sẽ quen cả A1 và B1
Tương tự: B2 cũng sẽ quen cả A1và B1
Lúc này ta có cách chia khác có nhiều cặp quen nhau hơn cách chia F là:
(A1,B2) (A2,B1), (A3,B3) và (A4,B4)