4,803 views
0 votes
0 votes

Suppose that there are nine students in a discrete mathematics class at a small college.

  1. Show that the class must have at least five male students or at least five female students.
  2. Show that the class must have at least three male students or at least seven female students.

1 Answer

1 votes
1 votes

FOR A

a) Assume for contradiction that the class has less than 5 male AND less than 5 female students.

Then the number of students in the class is:

C = M + F </= 4 + 4 = 8

But there are 9 in the class.

Hence the above assumption is false so statement A is true,

FOR B

Assume for contradiction that the class has less than 3 male AND less than 7 female students.

Then the number of students in the class is:

C = M + F </= 2 + 6 = 8

But there are 9 in the class.

Hence the above assumption is false so statement B is true,


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.

https://math.stackexchange.com/questions/443808/pigeonhole-principle-show-that-a-class-of-nine-has-at-least-five-male-or-five-f

Related questions

0 votes
0 votes
1 answer
3
admin asked Apr 29, 2020
2,324 views
How many numbers must be selected from the set $\{1, 3, 5, 7, 9, 11, 13, 15\}$ to guarantee that at least one pair of these numbers add up to $16?$
0 votes
0 votes
1 answer
4
admin asked Apr 29, 2020
778 views
How many numbers must be selected from the set $\{1, 2, 3, 4, 5, 6\}$ to guarantee that at least one pair of these numbers add up to $7?$