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,…

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

Answer 1

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.

Answer 2

Often it's useful in pigeonhole-type problems to try to make them not work, and when you see that you cannot, you often see why you cannot.

For example, if I say there are 2 electives and 9 students, can you see that at least 5 students must select the same elective? You can, because if you try to avoid putting 5 students in an elective, you end up with 4 in each and 1 left over.

Now apply this same approach to your problem. First ask what are the "pigeons" and what are the "holes"? The trick here is that you need to show that at least 6 students take exactly the same set of electives. How many ways can you enumerate 3 from 7? Those are your holes. Now you have 200 pigeons to place. Go.

Answer 3

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.

Answer 4

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)

Answer 5

First we must note that there are a total of $7 \choose 3$ options that the students can take. There is an option form where they can tick one of 35 boxes.

Now 200 students will be ticking these boxes. Using the pigeonhole principle. There are 200 pigeons and 35 pigeonholes. I hope this helps.