In a chess tournament there are players. On each day of the tournament, each player is designated to be 'white', 'black' or 'idle', and each 'white' player will play a game against every 'black' player. (You may assume that all games fixed for the day can be finished within that day.) At the end of the tournament, it was found that any two players have met exactly once. What is the minimum duration of days that the tournament lasts?
Solution
Clearly the tournament can be run in days if we assign, on day (where ),
* player to be 'white';
* players , , , to be 'black'; and
* all other players to be 'idle'.
In this way player and player (where ) would have met exactly once on day .
Now suppose the number of days is less than , and we would derive a contradiction. Note that we can assign a real number to each player , such that
(1) at least one is nonzero;
(2) the sum of all is zero; and
(3) the sum of the 's of all 'white' players on each day is zero.
This is because (2) and (3) represent a homogeneous system of fewer than linear equations in unknowns, and hence must have a nonzero solution (i.e. condition (1)). It follows that
Since any two players have met exactly once, we have
where and denote the set of 'white' and 'black' players on day respectively. Since the sum of the 's of all 'white' players on each day is zero, the above summation is equal to . On the other hand, as at least one is nonzero. This gives a contradiction to (4).