A society has to elect a board of governors. Each member of the society has chosen $10$ candidates for the board, but he will be happy if at least one of them will be on the board. For each six members of the society there exists a board consisting of two persons making all of these six members happy. Prove that a board consisting of $10$ persons can be elected making every member of the society happy.
Problem
Source: Baltic Way 2007
Tags: combinatorics proposed, combinatorics
pythag011
01.12.2010 06:57
Assume that such a board cannot be constructed.
Take some member of the society A. Either there is some person B whose list does not share any candidates with person A's list, or everyone's list shares candidates with person A's list. In the latter case, we can simply make the board of governors the 10 people on person A's list. Thus, there is some person B whose list does not share any candidates with person A's list.
Now, randomly split person A's list into two smaller lists of 5 candidates, A1 and A2. Do the same for person B, split his list into two smaller list of 5 candidates, B1 and B2.
Choosing Ai and Bj as the board must make someone unhappy, call this person Cij. Now consider the six people A,B,C11,C12,C21,C22. We can choose two candidates X and Y such that at least one of them appears on everyones list.
Either X or Y has to appear on A's list, and either X or Y has to appear on B's list. Because their lists are mutually disjoint, one of X/Y appears on A's list, and one of X/Y appears on B's list. WLOG, X is on A's list and Y is on B's list. Then, X is either in A1 or A2 (WLOG, A1.) and similarly Y is WLOG in B1. Then, neither X nor Y can be on C11's list, or someone from A1 and B1 would be on C11's list and choosing A1 and B1 as the board would make C11 happy, a contradiction.
meagain
27.08.2018 18:40
Any other solution to this? This one is out of nowhere! How he come to idea to split $A$?
fleurdelis
27.08.2018 20:18
How many people are in the society?