Cho một lớp học có 35 học sinh, các học sinh này tổ chức một số câu lạc bộ môn học. Mỗi học sinh tham gia đúng một câu lạc bộ. Nếu chọn ra 10 học sinh bất kì thì luôn có ít nhất 3 học sinh tham gia cùng một câu lạc bộ. Chứng minh có một câu lạc bộ gồm ít nhất 9 học sinh.
Đáp án: 9 học sinh
Cho một lớp học có 35 học sinh, các học sinh này tổ chức một số câu lạc bộ môn học. Mỗi học sinh tham gia đúng một câu lạc bộ. Nếu chọn ra 10 học sinh bất kì thì luôn có ít nhất 3 học sinh tham gia cùng một câu lạc bộ. Chứng minh có một câu lạc bộ gồm ít nhất 9 học sinh.
Đáp án: 9 học sinh
Giả sử tất cả các câu lạc bộ đều có không quá 8 học sinh.
Gọi n là số câu lạc bộ có hơn 1 học sinh.
+ Nếu thì từ 5 trong số các câu lạc bộ này, chọn mỗi câu lạc bộ 2 học sinh, khi đó 10 học sinh này không thỏa mãn điều kiện Bài toán.
+ Nếu thì khi đó số học sinh tham gia các câu lạc bộ này không quá
, nghĩa là còn ít nhất
học sinh, mỗi học sinh tham gia 1 câu lạc bộ mà câu lạc bộ này chỉ có 1 học sinh. Chọn 10 học sinh trong số này, không thỏa mãn điều kiện Bài toán.
Do đó .
Khi đó, số học sinh tham gia 4 câu lạc bộ này không quá nghĩa là còn ít nhất 3 học sinh, mỗi học sinh tham gia 1 câu lạc bộ mà câu lạc bộ này chỉ có 1 học sinh.
Chọn 2 trong số học sinh này và mỗi câu lạc bộ trên chọn 2 học sinh, khi đó 10 học sinh không thỏa mãn điều kiện.
Vậy điều giả sử sai, nghĩa là tồn tại một câu lạc bộ có ít nhất 9 học sinh tham gia.





