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 m·n/2: T > nm/2. On average, a student is a member in T/n committees and we find that T/n > m/2. Since, by the Pigeonhole Principle, the maximum value is at least the average value, there is indeed a student who is a member in more than m/2 committees.

Now let's prove by the mathematical induction that if m ≤ 2^k+1 - 2, for some k, then it is possible to select k students to chair m committees.

For k = 1, this is obvious. For, if k = 1, there is only one or two committees (m ≤ 2¹⁺¹ - 2 = 2.) By the first half of the problem, there is a student who is a member in more than half of the committees, which in this case is exactly the number of committees. Select this student to head the available committees.

Assume the assertion holds for m ≤ 2^k - 2, for some k. Increase the number of committees to 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 2^k+1 - 2^k - 2 = 2^k - 2. By the inductive assumption (k-1) students can be found to head those committees.

Reference

I. F. Sharygin, Mathematical Vinegrette, Mir, 2002 (in Russian)

71535698