Ta sẽ giải bài toán tổng quát:
Bài toán. Cho m là số nguyên dương lớn hơn 1. Có 2m học sinh tham
gia một buổi giao lưu. Biết rằng cứ 3 học sinh bất kỳ, đều có ít nhất
một cặp đôi gồm hai học sinh có trao đổi kinh nghiệm học tập với
nhau. Kí hiệu k là số cặp đôi như thế. Tìm giá trị nhỏ nhất của k.
Lời giải. Với mỗi số nguyên dương m > 1, rõ ràng tồn tại giá trị nhỏ
nhất của k, ta ký hiệu giá trị này bởi k(m).
Ta thấy k(2) = 2.
Bây giờ giả sử m > 2.
Xét một buổi giao lưu gồm 2m học sinh sao cho cứ 3 học sinh bất kỳ,
đều có ít nhất một cặp đôi gồm hai học sinh có trao đổi kinh nghiệm
học tập với nhau và số cặp đôi trao đổi học tập với nhau bằng k(m). Tồn tại ít nhất 2 học sinh (ký hiệu là A và B) không trao đổi học tập
với nhau, loại A và B ra khỏi buổi giao lưu này ta có một buổi giao lưu
gồm 2(m-1) học sinh mà cứ 3 học sinh bất kỳ, đều có ít nhất một cặp
đôi gồm hai học sinh có trao đổi kinh nghiệm học tập với nhau.
Số cặp đôi gồm hai học sinh có trao đổi kinh nghiệm học tập với nhau trong buổi liên hoan mới sẽ không ít hơn k(m − 1), mà mỗi học sinh
trong buổi liên hoan mới sẽ trao đổi kinh nghiệm học tập với A hoặc B
(vì A và B không trao đổi học tập với nhau), suy ra k(m) ≥
k(m − 1) + 2(m − 1).
Do đó k(m) ≥ m(m − 1) với mỗi số nguyên dương m>1. (1)
Với mỗi số nguyên dương m>1, ta xét một buổi giao lưu gồm 2m học
sinh như sau:
Các học sinh trong buổi giao lưu thuộc một trong hai nhóm (gọi là X
và Y). Nhóm X gồm m học sinh có trao đổi học tập từng đôi một,
nhóm Y gồm m học sinh có trao đổi học tập từng đôi một. Mỗi học
sinh của nhóm này đều không có trao đổi học tập với bất kỳ một học
sinh nào của nhóm kia.
Rõ ràng trong buổi giao lưu này, cứ 3 học sinh bất kỳ, đều có ít nhất
một cặp đôi gồm hai học sinh có trao đổi kinh nghiệm học tập với nhau
và số cặp đôi trao đổi học tập với nhau bằng m(m-1).
Suy ra k(m) ≤ m(m − 1) với mỗi số nguyên dương m>1. (2)
Từ (1) và (2) suy ra k(m) = m(m − 1) với mỗi số nguyên dương
m>1.
Trở lại bài toán ban đầu.
Theo trên ta có giá trị k bé nhất là k(21)=420