0
$\begingroup$

I am trying to understand an already solved problem which makes use of the pigeonhole principle

There are $271$ students in an exam which consists of $3$ random, non-repeating questions out of a pool of $10$, with no particular order. (this gives $10·9·8=720$ possible exams for $721$ participants)

  1. Show that at least $17$ students will have an exam with the same two first questions

The solution proceeds as follows:

There are $10·\frac{9}{2} = 45$ possible combinations of the first two questions

Then, as $270=45·16$, there are at least $16+1=17$ students with the same two first questions


  1. Show that at least $9$ students will have an exam with the same first and third questions

This other solution proceeds as follows:

There are $10·9 = 80$ possible combinations of the first and third questions

Then, as $720=90*8$, there are at least $8+1=9$ students with the same first and third >questions

I see that the pattern is showing that there are not "enough" exams with these combinations for the required number of students, but I do not understand the reasoning behind obtaining the possible combinations ($45$ and $80$).

Any help is appreciated! (I think that my problem is with Statistics!)

$\endgroup$
1
$\begingroup$

${10 \choose 2} =\frac {10!}{8!2!}= \frac {10*9}{1*2} = 45$.

You are choosing $2$ questions out of $10$. You have $10$ options for the first question you chose. And you have $9$ remaining options for the second question you choose. So there are $90$ ways to choose the two questions. But order doesn't matter. If you choose "What date did Washington cross the Delaware" first and "What is the airspeed velocity of the unladen swallow" second, that would be the same as if you had choosen "What is the airspeed velocity of the unladen swallow" first, and then chose "What date did Washington cross the Delaware".

So you divide the options in half. There are $45$ ways to choose the first two questions.

.....

$P(10,2) = \frac {10!}{8!} = 10*9=90$.

The second question order does matters. You must choose what will be question number #1. There are $10$ choices. Then you must choose what will be question number #3. There are $9$ remaining choices. So there are $10*9=90$ ways to list questions #1 and #3.

(Note a test where question #1 is "What date did Washington cross the Delaware" and question number #3 is "What is the airspeed velocity of the unladen swallow" is a different option than one where question #1 is "What is the airspeed velocity of the unladen swallow" and question #3 is "What date did Washington cross the Delaware")

$\endgroup$
  • $\begingroup$ Crystal clear, thank you very much. I wonder if these examples wouldn't create any issues like having questions expanding into others such as whether it's European or African swallows, but I guess that would be another problem! $\endgroup$ – Lightsong May 26 '20 at 16:21
1
$\begingroup$

Use the generalized pigeonhole principle: If more then $mr$ objects are distributed in $r$ classes then at least one class contains $m+1$ or more elements. For if not, then the totality of objects won't exceed $mr$. The classical pigeonhole principle is the case when $m=1$.

In the first problem $m=16,r=45$. We put two students in the same class if their first two problems are the same. Clearly there are $45$ classes. By the above principle there will be at least one class containing $17$ students.

The second question is similar.

$\endgroup$
  • $\begingroup$ The question wasn't how to use the pigeonhole principle; it was why is $r=45$...."Clearly there are 45 classes" as the OP specifically asked about this it clearly is nor "clear" $\endgroup$ – fleablood May 26 '20 at 15:11
  • $\begingroup$ OK. Since you have already answered that part, I am leaving my answer as it is with the hope that it may be useful for someone else. $\endgroup$ – Shahab May 27 '20 at 3:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.