This question is not so difficult but I have been quite fascinated with the way it was solved. It is stated as follow:
Given n students participating in a contest of m questions. At each stage, a student may choose to do the question in English or German or skip it. For every two questions, there exists a student who chooses to do both the questions and do them in different languages. What is the largest value that m can take
Hint: The answer to this question is $m \le 2^n$, you might expect where the binary system is used
I solved this problem, using mathematical induction. However, the solution using probability simply looks better! Any solution is appreciated!
There is a very simple solution with binary sequences and the pigeonhole principle.
Imagine a table whose rows are indexed by the $m$ questions, the columns are indexed by the $n$ students, and the entry for question $q$ and student $p$ is determined as follows:
If $p$ did not answer $q$, or $p$ answered $q$ in English, then the entry is $0$.
If $p$ answered $q$ in German, then entry is $1$.
Each question $q$ now has a row of $0$'s and $1$'s associated with it. I claim that any two different questions must have different binary sequences. Indeed, for every pair of questions, there exists a student whose answered one question in English and the other in German, implying one of the sequences has a $0$ in that place and other as a $1$.
Since there are $2^n$ possible binary sequences, and each of the $m$ questions has a different one, it must be the case that $m\le 2^n$. (This can be seen as an application of the pigeonhole principle; if you assumed $m\ge 2^n+1$, then having the questions be pigeons and the sequences be pigeonholes, then you would have two pigeons in the same hole, contradicting what was established before).