1 A certain exam consists of 5 multiple-choice questions, each with 4 different options, and each person selects exactly one option per question. Among 2000 answer sheets, there exists a number such that in any answer sheets, there are 4 sheets where any two of them have at most 3 answers in common. Find the minimum possible value of . (2000 China Mathematical Olympiad Problem)
Solution
1. The minimum possible value of is 25. Denote the 4 possible answers to each question as , and each test paper's answers as , where . For all 2000 answer sets , group those with the last 4 components identical into one class, resulting in classes. Since , there must be 8 test papers in the same class . Remove these 8 test papers, leaving 1992 test papers, of which 8 still belong to the same class . Remove these 8 test papers again, leaving 1984 test papers, of which 8 still belong to the same class . The 24 test papers removed belong to 3 classes . Therefore, when , any test papers taken from these 24 will have any 4 test papers with at least 2 belonging to the same class, which does not meet the problem's requirements, so . Now, construct such 2000 test papers, which have 250 different answers, with 8 test papers for each answer. These 250 different answers are any 250 of the answers that satisfy . Clearly, for any 2 different answers, they can have at most 3 components the same; otherwise, if 4 components are the same, then by the congruence, the 5th component would also be the same, which is a contradiction. In such 2000 test papers, any 25 taken will have at least 4 test papers that are pairwise different, and they can have at most 3 components the same, so meets the problem's requirements.