Bài 2
Các học sinh trong một lớp được chia thành các nhóm, mỗi nhóm có đúng ba thành viên, sao cho hai nhóm phân biệt bất kỳ có nhiều nhất một thành viên chung. Chứng minh rằng khi sĩ số lớp là 46, tồn tại một tập gồm 10 học sinh không chứa trọn vẹn nhóm nào.
Bước 2 trên 5: Giả sử ngược lại
Phân tích chi tiết
Giả sử s≤9. Với mỗi học sinh v ngoài S, tính cực đại cho thấy thêm v sẽ tạo ra một nhóm đầy đủ, nên có nhóm gồm v và hai học sinh trong S. Theo giả thiết giao nhau, mỗi cặp học sinh của S thuộc nhiều nhất một nhóm. Vì vậy có nhiều nhất nhị thức(s,2)≤36 học sinh bên ngoài được quy cho cách này.