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 1 trên 5: Chọn tập cực đại

Bước trước Bước tiếp

s=\max\{|S|:S\subseteq C,\ S\text{ contains no group properly}\}

Phân tích chi tiết

Gọi C là tập 46 học sinh và chọn tập S có kích thước lớn nhất nhưng không chứa trọn vẹn nhóm nào. Chỉ cần chứng minh s=|S| ít nhất bằng 10, vì khi đó mọi tập con 10 phần tử của S cũng có tính chất ấy.