In a country-level placement exam, there are 10 multiple-choice questions, each with 4 equivalent possible replies. What is the minimum number of students taking this exam, so that it is always possible to find at least 2 sets with at least 9 same replies? All questions must be answered (and we assume that they are answered at random, that is, without any previous knowledge of the subjects).
My thoughts: All possible different sets of replies are $4^{10}$. If we get $4^{9}+1$, do we ensure we will have at least 9 same sets?
Indeed, the minimum number is $4^9+1$. You can prove this works using the pigeonhole principle, with $4^9$ holes corresponding to the answers to the first $9$ questions.
To prove this is the minimum, you need to find a set of $4^9$ tests where no two agree on $8$ answers. From the pigeonhole argument, you know that every possible string of $4^9$ answers for the first $9$ questions must appear exactly once. You just need to choose the last answer for each of these in such a way that when any two answer sequences agree in $8$ places, their $10^{th}$ answers do not agree. Addition $\pmod 4$ is one way to accomplish this...