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).
Did you like this example?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee