# Another pigeonhole principle question

Have another question for you today:

A course has seven elective topics, and students must complete exactly three of them in order to pass the course. If 200 students passed the course, show that at least 6 of them must have completed the same electives as each other.

Now I know this is related to counting and the pigeonhole principle, and there are a couple of other related questions already asked but I couldn't apply them to my quuestion.

I know that the (informal) pigeonhole principle states that if you have $n$ boxes, and you have more than $n$ pigeons to distribute between those boxes, then at least one of the boxes will contain more than one pigeons, but I'm not sure what my boxes and what my pigeons are in this problem

-
If this is a homework, please tag it so. –  Thomas Connor May 20 '11 at 7:12
It's not homework. I'm trying to understand the principle in detail in preparation for a test –  Arvin May 20 '11 at 7:19

Instead of thinking about pigeons to be put into boxes, you could approach this the way Edsger Dijkstra does in http://www.cs.utexas.edu/users/EWD/transcriptions/EWD10xx/EWD1094.html

Specifically, he restates the principle this way

For a nonempty, finite bag of real numbers, the maximum is at least the average (and the minimum is at most the average).

This is a simple generalization of the familiar principle. In your case, let the bags be the number of possible selections of 3 electives out of 7 = $\binom{7}{3}$ =35.

Each bag is going to get a certain number of students. The number of students is always an integer $\geq 0$.

The average is 200/35 = 5.72 students per bag on average. The maximum out of the set of 35 bags must be greater than this average, i.e., at least 6 of the students must have completed the same set of 3 electives.

-

Note the generalized form of the pigeonhole principle: If more then mr elements are put in r classes then at least one class contains more then m elements. (You can prove it by contradiction, or just think about it intuitively. Also the normal pigeonhole principle follows by taking m=1.)

Now here we have r=35 classes (as $\tbinom{7}{3}=35$ ) and more then 35*5=175 students are being put in them. The result follows.(Let m=5)

-

Let us first count the number of topic choices. There are 7 course and a student must choose 3 among them. Therefore there are $${7 \choose 3} = 35$$ such choices.

Now there are 200 students. Suppose that there are at most 5 students that have completed the same electives as each other. We have $$5\times 35 =175.$$ But $175<200$ and therefore at least 6 students have completed the same electives.

-
Thanks Thomas, I see it now –  Arvin May 20 '11 at 7:30