There is a problem I have been struggling for a while and cannot seem to find the right avenue of solution.
Problem: An exam has $5$ multiple choice questions with $4$ choices each. 2000 students took the exam, each answering all 5 questions. It is found that $(*)$ for any $n$ exam papers, you can find $4$ papers such that any $2$ papers have at most $3$ same answers. Find the smallest $n$.
What I have: There are $1024$ different ways the exam can be answered. First find the number $m$ of different papers out of the $1024$ such that property $(*)$ is satisfied, then find the minimum $n$ exams out of the $2000$ exam papers that would include $m$ different exam answers. I tried formulating it as a graph, two exam types are connected if the differ in only $1$ answer, then each exam type is connected to exactly $15$ others. Then tried to use an inequality to bound the number of $m$, but it hasn't worked. The solution is $n=25$ which I believe means $m=13$.
Any hint or solution is welcome. Thanks.
I assume that by "the smallest $n$" we mean "the smallest $n$ for which it is possiblee for $(*)$ to hold" - so we get to pick the $2000$ exam papers however we like. In the worst case of exam papers, $(*)$ would not hold for any $n$: the worst case is that all $2000$ students give all the same answers.
To pick the exam papers in the best way possible, it's enough to just make sure that every set of answers is given at most twice. Then you are right that among any $n=25$ exams, there is a set of $m=13$ different exams.
Suppose that the $4$ choices for each question are assigned the numbers $0, 1, 2, 3$. Assign each exam paper a value by adding up the numbers for all its answers modulo $4$. Then any two exam papers with the same value either have all the same answers, or disagree in at least $2$ answers.
There are only $4$ possible values for an exam, so in any set of $m=13$ different exams, there are $\lceil \frac m4\rceil = 4$ exams with the same value. These are the $4$ exams we wanted to find.
There is an alternative construction. Suppose that the $2000$ students all give answers with value $0$ (by the same modulo $4$ rule as above), and that we evenly distribute their answers, so that each set of $256$ answers is given either $7$ or $8$ times. Then among any $25$ exam papers, there must be at least $4$ distinct answer sets. Those can be our set of $4$: since they all have value $0$, they differ in at least two places.
To complete the problem, we should also show that no matter what answers the students give, $(*)$ cannot hold for $n=24$.
To see this, group the exam papers into $256$ groups according to what the first four answers are. The average number of exams in a group is $\frac{2000}{256} = 7.8125$, so the average number of exams in three groups is $\frac{6000}{256} = 23.4375$. Therefore there's a set of three groups containing at least this average: at least $24$ exams.
Take the exams from those three groups. Then any $4$ of them include two exams from the same group. Therefore any $4$ of them have a pair of exams that differ in at most one answer, and $(*)$ does not hold for $n=24$.