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.

  • 1
    $\begingroup$ How many students are there... $\endgroup$ – Don Thousand Jun 14 '19 at 16:39

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.