Suppose there is a test with $n\geq 2$ questions each of which will receive a score from 0 to $m\geq 1$. Every possible score is obtained by some unique student. Define same$(a,b)$ to be the set of questions that students $a$ and $b$ get the same score on. I need to show that there are some four students $a,b,c,d$, at least three distinct, such that same$(a,b)=$same$(c,d)$. I am also required to show this using the Pigeon Hole Principle.
Now I think I can solve it without the PHP. Some two students must match on all but the last question and differ in the last. Some other student must have exactly opposite scores (i.e. mismatched) on all but the last question, and on the last, have a score call it x. Some fourth student must match the most recent on all but the last question, and on that one, get something other than x. The first two match on the same set as the last two.
But how to do this with the PHP? I know there are $(m+1)^n$ scores and therefore students. The number of sets of matching scores is just the number of subsets of problems, $2^n$. From here I'm not sure what I can infer.
Best Answer
There are $$ \binom{(m+1)^n}{2} \qquad $$ sets $\{x,y\}$ of two distinct students.
There are $2^n$ possibilities for the set $\text{same}(x,y)$. \begin{align*} \text{Then}\;\;&\binom{(m+1)^n}{2}\\[4pt] \ge\;&\binom{2^n}{2}\;\;\;\;\;\;\;\text{[since $m\ge 1$]}\\[4pt] =\;&\frac{(2^n)(2^n-1)}{2}\\[4pt] =\;&2^n\left(\frac{2^n-1}{2}\right)\\[4pt] \ge\;&2^n\left({\small{\frac{3}{2}}}\right)\;\;\;\,\text{[since $n\ge 2$]}\\[4pt] >\;&2^n \end{align*} hence, by the pigeon hole principle, there are two distinct sets $\{a,b\}$ and $\{c,d\}$ of two distinct students such that $\text{same}(a,b)=\text{same}(c,d)$.
Since $a\ne b$, $c\ne d$, and $\{a,b\}\ne\{c,d\}$, it follows that at least $3$ of $a,b,c,d$ are distinct.