一道锻炼思维的好题-组合题【四星】

原题：学校设置了大量选修课供学生选择，已知某个小组9名同学中，任何3名学生都有两人选同一门课，但每人最多只能选3门课。请说明至少有3人选择了同一门选修课。


请先考虑20分钟……

 
解析：
设9名同学分别是P1、P2…P9，课程分别为C1、C2、C3……
考虑应用反正法，假设一门课最多只有两人报名，如果根据这个假设推导出与原题条件相矛盾的结论，那么也就证明假设存在错误，也就是一门课会有超过2人报名，这样就间接的证明了原题结论，即至少有3人选择同一门课。

根据假设，一门课最多只有两人报名，那么最少有几门课？

课程要最少，自然要求报名的人少，9名学生中，可以有1人报0门，因为如果有2人报0门，那么这两人与其他任何一人组成的3人组不满足“任何3名学生都有两人选同一门课”的条件。剩下8人都需要报课程，两人组合共有28种（8*7/2）。

这28中组合都报了不同的课程，因为如果有两个组合如P1、P2和P3、P4报了相同的课程，那么P1、P2、P3这三人就选择了同一门课了。所以至少有28门课。已知，每人最多只能选3门课，9人最多选27门不同的课，如果是28门课那么只能有同学选的课程大于3门，与原题条件矛盾。
所以，假设错误，也即是至少有3人选择同一门课。


还有一种解释，仍然是反正法，我们假设每门选修课最多2人报名。
对于P1，根据题意他最多选3门课，设为C1、C2、C3，那么他最多只有三个同学P2、P3、P4，假定（P1、P2）选C1，（P1、P3）选C2，（P1、P4）选C3，P1不能有同样选C1或C2或C3课程的第四名同学了，因为如有，直接就满足至少有3人选择同一门课。同样的道理，P5选课程C4、C5、C6，也最多只有三名同学，假设为P6、P7、P8。此时P9与P5、P1的三人组没有任何两人选择的课程相同。与题意不符。假设错误，因此至少有3人选择同一门课。