understanding a pigeonhole principle problem

Question

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

---

2. 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!)

Answer 1

${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")

Answer 2

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.