Maths Olympiad Prep

Library / /199 of 520

Combinatorics Difficulty 6.4 National olympiad Find the answer

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 nn such that in any nn answer sheets, there are 4 sheets where any two of them have at most 3 answers in common. Find the minimum possible value of nn. (2000 China Mathematical Olympiad Problem)

A number or a short expression. Spacing and $ signs are ignored.

Solution

1. The minimum possible value of nn is 25. Denote the 4 possible answers to each question as 1,2,3,41, 2, 3, 4, and each test paper's answers as (g,h,i,j,k)(g, h, i, j, k), where g,h,i,j,k{1,2,3,4}g, h, i, j, k \in \{1,2,3,4\}. For all 2000 answer sets (g,h,i,j,k)(g, h, i, j, k), group those with the last 4 components identical into one class, resulting in 44=2564^4 = 256 classes. Since 2000=256×7+2082000 = 256 \times 7 + 208, there must be 8 test papers in the same class AA. Remove these 8 test papers, leaving 1992 test papers, of which 8 still belong to the same class BB. Remove these 8 test papers again, leaving 1984 test papers, of which 8 still belong to the same class CC. The 24 test papers removed belong to 3 classes A,B,CA, B, C. Therefore, when n24n \leqslant 24, any nn 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 n25n \geqslant 25. 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 44=2564^4 = 256 answers (g,h,i,j,k)(g, h, i, j, k) that satisfy g+h+i+j+k0(mod4)g + h + i + j + k \equiv 0 \pmod{4}. 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 n=25n = 25 meets the problem's requirements.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.