A Russian problem from the 1999 Mathematical Olympiad:
In an election, each voter writes the names of n candidates on his ballot. Each ballot is then placed into one of n+1 boxes. After the election, it’s noted that each box contains at least one ballot, and that if one ballot is drawn from each box, these n+1 ballots will always have a name in common. Show that for at least one box, there’s a name that appears on all of its ballots.
|
SelectClick for Answer |
Suppose, by way of contradiction, that this isn’t the case — that there is no box whose ballots all show a common name. Look at an arbitrary ballot in the first box. It lists n names; call these Candidates 1 through n. Now we can find a ballot in the second box that doesn’t list Candidate 1, a ballot in the third box that doesn’t list Candidate 2, and so on. Collect these n+1 ballots together and they form a group with no name in common. This contradicts the stated fact that no such group exists. So our assumption must be wrong: All of the ballots in at least one box must have a name in common.
|
