Maths Olympiad Prep

Library / /76 of 136

Combinatorics Difficulty 8.0 National Olympiad, round 2 Prove it Hong Kong

In a chess tournament there are 100100 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 9999 days if we assign, on day kk (where 1k991 \le k \le 99),

* player kk to be 'white';
* players k+1k + 1, k+2k + 2, \ldots, 100100 to be 'black'; and
* all other players to be 'idle'.

In this way player ii and player jj (where 1i<j1001 \le i < j \le 100) would have met exactly once on day ii.

Now suppose the number of days is less than 9999, and we would derive a contradiction. Note that we can assign a real number xix_i to each player ii, such that
(1) at least one xix_i is nonzero;
(2) the sum of all xix_i is zero; and
(3) the sum of the xix_i's of all 'white' players on each day is zero.

This is because (2) and (3) represent a homogeneous system of fewer than 100100 linear equations in 100100 unknowns, and hence must have a nonzero solution (i.e. condition (1)). It follows that
0=(x1+x2++x100)2=(x12+x22++x1002)+21i<j100xixj.(4) 0 = (x_1 + x_2 + \cdots + x_{100})^2 = (x_1^2 + x_2^2 + \cdots + x_{100}^2) + 2 \sum_{1 \le i < j \le 100} x_i x_j. \quad (4)
Since any two players have met exactly once, we have
1i<j100xixj=k(wWkxwbBkxb) \sum_{1 \le i < j \le 100} x_i x_j = \sum_k \left( \sum_{w \in W_k} x_w \sum_{b \in B_k} x_b \right)
where WkW_k and BkB_k denote the set of 'white' and 'black' players on day kk respectively. Since the sum of the xix_i's of all 'white' players on each day is zero, the above summation is equal to 00. On the other hand, x12+x22++x1002>0x_1^2 + x_2^2 + \cdots + x_{100}^2 > 0 as at least one xix_i is nonzero. This gives a contradiction to (4).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.