2008 iTest Problems/Problem 28

Problem

Of the thirteen members of the volunteer group, Hannah selects herself, Tom Morris, Jerry Hsu, Thelma Paterson, and Louise Bueller to teach the September classes. When she is done, she decides that it's not necessary to balance the number of female and male teachers with the proportions of girls and boys at the hospital month, and having half the women work while only of the men work on some months means that some of the women risk getting burned out. After all, nearly all the members of the volunteer group have other jobs.

Hannah comes up with a plan that the committee likes. Beginning in October, the committee of five volunteer teachers will consist of any five members of the volunteer group, so long as there is at least one woman and at least one man teaching each month. Under this new plan, what is the least number of months that go by (including October when the first set of five teachers is selected, but not September) such that some five-member committee taught together twice (all five members are the same during two different months)?

Solution

There are a total of ways to pick any five people. However, there are ways to pick groups that are all women and ways to pick groups that are all men. Thus, there are ways to pick mixed gender groups, so by the Pigeonhole Principle, it takes months to guarantee that at least one five-member committee taught twice.