解题随笔2

下面是一道运用抽屉原理的经典竞赛题，出自第29届IMO预选题，通过分析这道题的解题思路，我想谈谈在探索思路时如何从一些失败的尝试中得到一些经验。
问题：49个学生解3个问题，每个题的得分是0分到7分的整数.求证：存在两个学生A和B，对每个问题，A的得分不少于B.
分析1：解决组合问题，我们一般都会选择一般化和特殊化，先给出这个问题的一般形式，然后再用更小的特殊值进行尝试，初看这道题，很多人都会认为，所以问题或许可以一般化为：一般化问题：个学生解3个问题，每个题的得分是0分到分的整数.求证：存在两个学生A和B，对每个问题，A的得分不少于B
但取，很容易发现这个一般化是错的，4个学生不太够，得分可能性个数和学生之间肯定存在关系，但关系应该不会很简单，这里的应该只是巧合
分析2：既然不能从学生和分数之间一般化，那只能考虑从问题数上特殊化了，仔细体会下，大家应该都能感觉到问题数是这道题的难点所在，当问题数增加时，两个学生的得分关系变得异常复杂，很难看清他们之间的偏序结构，特殊化为一个问题太显然，没有任何启发，所以我们考虑特殊化为2个问题：特殊化问题：至少多少个学生解2个问题，每个题的得分是0分到7分，才能保证：一定存在两个学生A和B，对每个问题，A的得分不少于B
分析2.1：首先来猜答案，我们希望选择尽量多的学生，两两之间的得分没有绝对优势(每个人不可能每道题的得分都不少于另一个人)，利用贪心策略，我们自然会选择这些得分：，所以只要有9个学生，就能满足题目的结论
分析2.2：下面利用抽屉原理说明9是最小值，显然应该构造8个抽屉，把刚刚的8个分数分别归入其中一个抽屉，最自然的想法是根据第一题得分来构造抽屉，得分为的归入第个抽屉，此时正好有8个抽屉，如果有9个人，则必有两人第一题得分相同，所以只需比较他们的第二题的得分，就能确定得分的绝对优势。而且我们还发现实际上我们是讲问题化归到“1个问题”的情形
总结2.3：通过这个分析，我们解决了特殊化问题，而且获得了一些启发：如果两个人第一题得分相同，则在两道题上一定存在得分绝对优势
分析3：下面我们沿用这个策略来解决原始问题：
分析3.1：根据第一题得分构造8个抽屉，根据抽屉原理，一定有7个人在第一题通分，但根据上面的特殊化问题，需要至少9个人，现在人不够？抽屉构造失败！分析3.2：下面分析失败原因，按照上面特殊化问题构造抽屉的思路，我们实际上找到的两个人在第1题得分上相同，而在第2题得分上不同，在解决原始问题时，如果抽屉原理能成功，我们实际上找到的两个人在前两题上得分都相同，这个限制太强了，原来的结论只是要找两个学生在得分上绝对优劣势，而按我们构造的抽屉，要找到的两个人在两道题上得分都需要一样，简单思考下就会发现，这个对学生数的限制要大很多！分析3.3：下面根据前面失败的经验来修改我们的抽屉，必须记住：最终根据抽屉原理得到的两个学生，不需要保证在两道题上得分相同！但正常情况下，我们肯定是根据某些得分来划分抽屉，所以抽屉原理的结果一定是两个学生在某道题上得分相同，所以我们只能根据前两题的得分构造抽屉，每个抽屉里前两题的得分必须有“绝对优劣势”，有大小关系而不是相等关系！另外根据抽屉原理，我们必须保证某个抽屉里有9个人，才能得到有两个人第三题同分，所以只能有6个抽屉！分析3.4：不妨设任意两名学生前两题的得分不完全相同，为了解释更直观，我们讲前两题的得分看成坐标，画在平面直角坐标系里，为了保证有抽屉里的点超过8个，而且两点坐标有“绝度优势”，又不能根据得分完全相同来划分抽屉，这自然得到下面的构造方法：
分析3.5：上图是构造方法，不同颜色代表不同抽屉，但这样做有8个抽屉，超了！这里需要一些巧妙的变通，仔细看图，最左上角的几个抽屉里的得分数量很少，如果有6个抽屉，我们需要找到的抽屉里有9个点，所以我们可以把这些抽屉进行合并，不过合并后这些抽屉里的点的坐标没有“绝对优势”，所以必须保证这些抽屉里的点的个数不超过8个，这样不会选到他们，按下图重新构造
把左上角的4个抽屉合并成两个，根据抽屉原理，有个抽屉的点数不少于9个，而且一定不是左上角的两个抽屉，问题得证分析4：最后我们再说明下，49实际上是最优值，对于48个学生，无法保证原题结论成立，下面我们再用上面的坐标图结合贪心策略，给出一个例子，我们还是先限制在前两题的得分上，我们考虑将前两题的得分没有“绝对优势”的点尽量并在一起，构成一类，并让它们的第3题得分相同，不同类的第3题得分不同，为了保证不同类的点得分没有“绝对优势”，最好能保证类与类的前两题得分有“绝对优劣势”，这样可以通过给有“绝对优势”的类在第3题上赋更低的分，保证类与类的点没有“绝对有劣势”，因为第3题上只有8种得分，所以最多只能分8类，下面是构造方法：
分析5：同一条斜线上的点属于同一类，从左下方到右上方，第3题得分依次递减：，因为右上方的类的前两题得分和更大，所以在前两题上不可能比左下方的类处于“绝对劣势”，但在第3题得分上低于左下方的类，所以它们之间不可能存在“得分优劣势”，所有类恰好有48个点，构造完成
拓展1：按照这种贪心策略的构造，如果讲7分改成分，容易猜出原题答案应该可以推广为，有兴趣的人可以自行证明
拓展2：除了这种构造抽屉的方法，原始题还有其他构造，可以参看：《IMO50年第6卷：1985~1989》
下面是一道经典智力题，大家可以做一做，体会一下如何从尝试中获得一些经验，逐步修正，另外这道题还可以通过拓扑变形得到一个非常有启发性的解法，大家也可以想想：
点击在看并截图留言，可以获得这道题智力趣题的两种解法哦！