CMI2014-B-02

Question

There are $n$ students in a class. The students have formed $k$ committees. Each committee consists of more than half of the students. Show that there is at least one student who is a member of more than half of the committees.

Answer 1

Consider a table with one row for each student and one column for each committee. The table has 1 in the row corresponding to a student s and the column corresponding to a committee c if the student s is a member of the committee c. The table has 0 in the row corresponding to a student s1 and the column corresponding to a committee c1 if the student s1 is not a member of the committee c1. Since each committee consists of more than half of the students, each column of the table has more than half its entries as 1. Hence, there are more than n*k/ 2 entries in the table that are 1. Hence, there is at least one row in the table with more than half its entries as 1 (otherwise, it is not possible to have more than n×k 2 entries in the table that are 1). This row corresponds to a student who is a member of more than half of the committees.