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

gvaldytist 2022-06-25 Answered
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
You can still ask an expert for help

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

Arcatuert3u
Answered 2022-06-26 Author has 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).
Did you like this example?
Subscribe for all access

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2021-09-08

A restaurant offers a $12 dinner special with seven appetizer options, 12 choices for an entree, and 6 choices for a dessert. How many different meals are available when you select an appetizer, an entree,and a dessert?

asked 2021-09-09
In a fuel economy study, each of 3 race cars is tested using 5 different brands of gasoline at 7 test sites located in different regions of the country. If 2 drivers are used in the study, and test runs are made once under each distinct set of conditions, how many test runs are needed?
asked 2022-08-18
How many possible 10-digit phone numbers with the area code 548 are there? (any decimal digit can be the digit of a phone number. For instance the number 548−050−5000 is a possible phone number)
asked 2022-10-26
I got 1 red ball, 1 blue, 2 yellow, 3 green, totally 7 balls. I wanna select 3 balls from them. How many ways I can do this?I counted manually
123,124,133,134,144,233,234,244,334,344,444,
so 11 combinations.Is there a formula for it?
asked 2021-01-04
Suppose a class consists of 5 students majoring in Computer Science, 5 students majoring in Chemistry and 3 students majoring in Mathematics. How many ways are possible to form a group of 3 students if each group should consist at most 2 students majoring in Computer Science?
asked 2022-09-11
How many 8 digit numbers are there that contain both a 5 and a 6?
Number of 8 digit numbers containing both a 5 and a 6
= Number of 8 digit numbers - Number of 8 digit numbers lacking both a 5 and a 6
= 90000000 7 8 7
= 75319936
Does this seem right?
asked 2022-05-19
My idea is that by finding the combination of arranging the 10 bears into the sample, this can be used to calculate the probability. For example, this would be 10 C 5 = 30240. However, how would I calculate the number of arrangements of the four bears that will go into the sample? I considered 5 C 4 , yet this would be illogical as it only includes the number of arrangements of the four bears in the sample, but does not consider the arrangements in the sample not selected. Is my working correct?

New questions