# Given n students participating in a contest of m questions. At each stage, a student may choose to d

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
You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Arcatuert3u
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).