趣题：鸽笼原理的应用 IMO 2001 Problem #3

    IMO 2001第三题：21个女生和21个男生一起参加了一场数学竞赛。结果显示，每个参赛者最多做对了6道题，并且对于任一对男生和女生，至少有一道他们都做对了的题。
    求证：存在这样的一道题，至少有三个女生和三个男生同时做对。

    当然，这个题目背景无趣而又生硬。如果是我的话，我肯定会把题目改成下面这个样子：21个女生和21个男生参加速配游戏，每个人独立地在自己的纸上写下不超过6种兴趣爱好。结果显示，对于任一对男女，他们都写下了至少一个相同的爱好。求证，存在某一个兴趣爱好，有至少三男三女都把它写上了。

    我是一个忠实于原题的好娃娃，因此还是用数学竞赛来当题目背景。对于每个问题，如果有至少3个男生答对了，就给这个问题添加一个标记“B”；如果有至少3个女生答对了，就给这个问题添加一个标记“G”。然后我们画一张21×21的表格，横行代表男生，纵列代表女生。每一个格子都代表一道对应的男女同时做对的题（不同的格子可能对应相同的题目），我们把对应的题目的“B”、“G”标记填进格子里。
    下面我们说明，每一横行里至少有11个格子标了“G”，每一个纵列里至少有11个格子标了“B”。考虑某一个特定的人，他（她）与每一个异性参赛者都有同时答对的题目，但他（她）自己最多只做出6道题。这6道题目需要“分配”给21个异性参赛者。我们希望知道最多有多少道题被不超过2个异性参赛者答对。显然，最极端的情况就是其中的5道题目每道分别被2个异性做对，剩下的第6道题被其余11个异性做对。反过来这也就是被至少三个人答对的题目最少的情况，因此每一行（列）里都有至少11个格子标有异性的标记。
    这样，我们就有了至少21*11个标有“G”的格子，和至少21*11个标有“B”的格子。但21*11*2 > 21*21，因此总有一个格子被同时标上了“G”和“B”。

来源：http://www.cut-the-knot.org/pigeonhole/BoysGirlsProblems.shtml

10 条评论

发表评论

  +  1  =  5