Pigeonhole principle: show that a class of nine has at least five male or five female students.

Question

Here is the problem in full, start to finish, with no other special instructions or rules:

"If there are 9 students in a class, show that at least 5 must be male or at least 5 must be female. Also, show that at least 3 are male or at least 7 are female."

I assume that this is a pigeonhole principle problem, because it was the last topic covered. However, what I don't get is why there must be at least 5 male or at least 5 female students. And if there must be 5 of one or the other, then how is it possible to satisfy the second part of the question which says to show that 7 are female?

A class could easily have 9 male and 0 female students, or 0 male and 9 female students. There is no rule or note anywhere that says that each student must be the opposite gender of the previous one or anything like that. The above is the question in full.

Answer 1

The pigeonhole principle is basically a counting argument that says if you have n items to put into m pigeonholes with n > m, at least on pigeonhole must contains more than one item.

In this particular case, there are 9 students (items) and 2 pigeonholes (genders), so when you have assigned gender to 8 students, you either already have a group (pigeonhole) with 5 students of the same gender, or you have two groups, each with four students. Therefore, regardless of the gender of the 9th student, one of the groups must end up with 5.

Similarly, after you've assigned gender to 6 students, either there were already 3 males, or there were 0, 1 or 2 males. You still have 3 more students, so if there were 0 males, there must have been 6 females, and either the 3 remains students are all males (in which case, there will be 3 males) or one of the is a female (in which case, there will be at least 7 females). The argument for 1 or 2 males out of the 6 is similar.

Answer 2

Suppose to the contrary there are fewer than $3$ males and fewer than $7$ females. Then there could be at most $2+6$ people in the class. (We are tacitly assuming that male and female are the only options.)

Essentially the same argument works for the $5$ and $5$ question.

Answer 3

Suppose that neither the number of boys nor the number of girls is at least five. Then both are at most four, hence there can only be at most $8$ students, whether male or female. This is a contradiction since we know there are $9$ students.

Answer 4

Well, if there are at least 5 males, then that means that the number of females must be at most 4, since any other number would lead to a number greater than 9. It follows that, if there are at least 5 females, then there must be at most 4 males, since, again, otherwise there would be more than 9 in the group. The same reasoning can be used for the second part.

If there are at least 3 males, then there can be at most 6 females, since otherwise the total would again be greater than 9. It follows that, if there are at least 7 females, then the number of males cannot exceed 2, since otherwise, once again, the total number of people in the group would be greater than 9.