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

gvaldytist

gvaldytist

Answered question

2022-06-25

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 2 n , you might expect where the binary system is used

Answer & Explanation

Arcatuert3u

Arcatuert3u

Beginner2022-06-26Added 30 answers

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 2 n (This can be seen as an application of the pigeonhole principle; if you assumed m 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).

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?