## Committee Chairs

[Sharygin, p. 12]. Assume in a class of students each of the number of committees contains more than half of all the students. Prove that there is a student who is a member in more than half of the committees. If the number of students is 30, it is possible to select 4 students to be committee chairs so as not to leave a chairless committee. (Committees may be only chaired by their own members.)

Let's n be the number of students and m the number of committees in the class. The total committee membership T exceeds

Now let's prove by the mathematical induction that if ^{k+1} - 2,

For k = 1, this is obvious. For, if k = 1, there is only one or two committees ^{1+1} - 2 = 2.)

Assume the assertion holds for ^{k} - 2,^{k+1} - 2. By the first half of the problem, there is a student who is a member in more than half of the committees, which is 2^{k}. After this student has been selected to head those committees, the number of committees awaiting a chair will not exceed ^{k+1} - 2^{k} - 2 = 2^{k} - 2.

### Reference

|Contact| |Front page| |Contents| |Did you know?| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny