某次考试有 $5$ 道选择题，每题都有 $4$ 个不同答案供选择，每人每题恰选 $1$ 个答案．在 $2000$ 份答卷中发现存在一个 $ n$，使得任何 $n$ 份答卷中都存在 $4$ 份，其中每两份的答案都至多 $3$ 题相同．求 $n$ 的最小可能值．
【难度】
【出处】
2000第15届CMO试题
【标注】
【答案】
略
【解析】
$n$ 的最小可能值为 $25$．
将每道题的 $ 4$ 种答案分别记为 $1,2,3,4$．每份试卷上的答案记为 $(g, h, i, j, k)$，其中 $g, h, i, j, k \in\{1,2,3,4\}$，令 $\{(1, h, i, j, k),(2, h, i, j, k),(3, h, i, j, k),(4, h, i, j, k)\},h, i, j, k=1,2,3,4$ 共得 $256$ 个四元组．由于 $2000 = 256\times 7 +208$，故由抽屉原理知有 $8$ 份考卷上的答案属于同一个四元组，取出这 $8 $ 份考卷后，余下的1 992 份中仍有8 份属千同一个四元组；再取出这8 份考卷，余下的 $1 984 $ 份中又有 $8$ 份属于同一个四元组；取出这 $ 8$ 份考卷，连同前两次取出的考卷共 $24$ 份 在这 $ 24$ 份考卷中，任何 $4 $ 份中总有两份的答案属于同一个四元组，当然不满足题中的要求 所以，所求的最大值大于等于 $25$．
另一方面，令 $\begin{aligned} S=&\{(g, h, i, j, k) | g+h+i+j+k= 0(\bmod 4), g, h, i, j, k \in\{1,2,3,4\} \} \end{aligned}$ 则 $|S|=256$，且 $S$ 中任何两种答案都至多有 $3$ 题相同．从 $S$ 中去掉 $6$ 个元素，当余下的 $250$ 种答案中的每种答案都恰有 $8$ 人选用时，共得到 $2000$ 份答卷，其中的任何 $25$ 份答案中，总有 $4$ 份不相同，由于它们都在 $S$ 中，当然满足题中要求这表明 $n =25$ 时可以满足题中要求．
综上可知，所求的 $n$ 的最小可能值为 $25$．
将每道题的 $ 4$ 种答案分别记为 $1,2,3,4$．每份试卷上的答案记为 $(g, h, i, j, k)$，其中 $g, h, i, j, k \in\{1,2,3,4\}$，令 $\{(1, h, i, j, k),(2, h, i, j, k),(3, h, i, j, k),(4, h, i, j, k)\},h, i, j, k=1,2,3,4$ 共得 $256$ 个四元组．由于 $2000 = 256\times 7 +208$，故由抽屉原理知有 $8$ 份考卷上的答案属于同一个四元组，取出这 $8 $ 份考卷后，余下的1 992 份中仍有8 份属千同一个四元组；再取出这8 份考卷，余下的 $1 984 $ 份中又有 $8$ 份属于同一个四元组；取出这 $ 8$ 份考卷，连同前两次取出的考卷共 $24$ 份 在这 $ 24$ 份考卷中，任何 $4 $ 份中总有两份的答案属于同一个四元组，当然不满足题中的要求 所以，所求的最大值大于等于 $25$．
另一方面，令 $\begin{aligned} S=&\{(g, h, i, j, k) | g+h+i+j+k= 0(\bmod 4), g, h, i, j, k \in\{1,2,3,4\} \} \end{aligned}$ 则 $|S|=256$，且 $S$ 中任何两种答案都至多有 $3$ 题相同．从 $S$ 中去掉 $6$ 个元素，当余下的 $250$ 种答案中的每种答案都恰有 $8$ 人选用时，共得到 $2000$ 份答卷，其中的任何 $25$ 份答案中，总有 $4$ 份不相同，由于它们都在 $S$ 中，当然满足题中要求这表明 $n =25$ 时可以满足题中要求．
综上可知，所求的 $n$ 的最小可能值为 $25$．
答案
解析
备注
