A problem from Crux Mathematicorum, April 2006:
A group of people must be formed into committees. Show that the number of possible committees that can be formed with an odd number of members is the same as the number that can be formed with an even number of members. (Assume that a committee with no members and one that includes everyone are both allowed.)
|
SelectClick for Answer |
This solution is by Geneviève Lalonde. Call a committee an even committee if it has an even number of members and an odd committee if it has an odd number of members.
If the total number of people in the group is odd, then for each even committee the total number of remaining people is odd (and thus constitutes an odd committee). And vice versa: For each odd committee, the number of people who aren’t in that committee is even and constitutes an even committee. So there’s a one-to-one correspondence between the even and odd committees, and their numbers must be equal.
If the total number of people in the group is even, then consider one person (call him John). For each even committee C that doesn’t contain John, there’s a corresponding odd committee made up of everyone who’s not in C except for John. And for each even committee C that contains John, there’s a corresponding odd committee made up of John plus everyone who’s not in C. So again there’s a one-to-one correspondence between the even and odd committees, and we conclude that their numbers are equal.
|
