5
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks Thomas, I see it now $\endgroup$ – Arvin May 20 '11 at 7:30
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ahh, I see, so you need to work out the total number of possible combinations of topics, which is the boxes/holes. Since the topics cannot be repeated in the choices (you can only select a topic once) then I suppose we need to use the choose formula c(7,3) right? $\endgroup$ – Arvin May 20 '11 at 7:25
  • $\begingroup$ @Arvin: Yes, c(7,3) is correct. I was leaving that part for you to work out, but I see other respondents did the whole problem shortly after. Ah well. $\endgroup$ – Fixee May 20 '11 at 14:21
2
$\begingroup$

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)

$\endgroup$

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.