math-ai/BlueMO

1{2    "source_file": "./raw_volume-zh/volume14/chapter4.tex",3    "problem_type": "calculation",4    "problem": "例11. 某次考试有 5 道选择题, 每题都有 4 个不同的答案供选择, 每人每题恰选 1 个答案.\n在 2000 份答卷中发现存在一个 $n$, 使得任何 $n$ 份答卷中都存在 4 份, 其中每两份的答案都至多有 3 道题相同.\n求 $n$ 的最小可能值.",5    "solution": "解:将每题的四个选项依次记为 $1,2,3,4$, 每份答案记为 $(a, b, c, d$, $e)$, 其中 $a, b, c, d, e \\in\\{1,2,3,4\\}$.\n对给定数组 $(a, b, c, d), a, b, c, d \\in\\{1,2,3,4\\}$, 将 2000 份答卷中答案为 $(a, b, c, d, 1),(a, b, c, d, 2),(a, b, c, d, 3),(a, b, c, d, 4)$ 的答卷归为一类, 这样共 $4^4=256$ 类.\n由抽屉原理, 至少有 $\\left\\lceil\\frac{2000}{256}\\right\\rceil=8$ 份答卷属于一类.\n不妨取其中 8 份答卷作为 $A$ 组答卷; 在剩下的答卷中, 同理至少可取出 $\\left\\lceil\\frac{1992}{256}\\right\\rceil=8$ 份, 作为 $B$ 组答卷; 剩下的答卷中仍至少可取出 $\\left\\lceil\\frac{1984}{256}\\right\\rceil=8$ 份, 作为 $C$ 组答卷.\n在 $A, B, C$ 组这 24 份答卷中, 根据抽屉原理, 任意 4 份答卷必有两份在一组, 则它们至少有 4 题答案相同.\n所以 $n \\geqslant 25$.\n另一方面,当 $n=25$ 时,构造如下 2000 份答卷:\n取 250 组不同的数组 $(a, b, c, d), a, b, c, d \\in\\{1,2,3,4\\}$, 对其中每个数组, 取 $e \\in\\{1,2,3,4\\}$ 使得 $a+b+c+d+e$ 是 4 的倍数, 对这样一组 ( $a$, $b, c, d, e)$, 令 8 份答卷写有这样的答案, 共 2000 份答卷.\n任取其中 25 份答卷, 必有 4 份答案两两不同, 再根据数组 $(a, b, c, d, e)$ 的取法可知, 其中任何两份答卷至多只有 3 题答案相同.\n综上可知, $n$ 的最小可能值为 25 .",6    "remark": "注:本题的表述比较复杂, 应先仔细分析题目要求.\n方面我们要构造 2000 份答卷, 尽可能使比较小的 $n$ 满足题意; 另一方面又要找到尽可能大的 $k$, 使得任意 2000 份答卷都不满足题意, 即存在 $k$ 份答卷, 使得其中任何 4 份答卷中, 总有两份的答案至少有 4 题一致.\n在上述两方面的讨论中, \"任何 $n$ 份答卷\"、\"任意 2000 份答卷\"、\"任何 4 份答卷\"这些表述均涉及到答卷的任意性, 而要处理的又是存在性问题, 于是抽屉原理便有了用武之地(注意在解答最后一步验证\"25 份答卷中必有 4 份答案两两不同\"时,也用了抽屉原理: 假设 25 份答卷中只出现 3 种不同的答案, 那么必有一种答案出现超过 8 次).\n抽屉原理是解决存在性问题的有力工具.\n抽屉原理本身并不难,难在如何运用它去解决问题.\n在具体问题中如何制造抽屉, 希望本节的例题对读者能有所启示.",7    "figures": []8}