Maths Olympiad Prep

Library / /5 of 7

Combinatorics Difficulty 5.1 AIME, harder Prove it Hong Kong

In a chess tournament, there were nn contestants and any two of them played at most one game against each other. Each contestant has played exactly 100100 games. For any two contestants AA and BB who had played against each other, there were exactly 5050 other participants who have played against both AA and BB. On the other hand, for any two contestants CC and DD who had not played against each other, there were exactly 44 other participants who have played against both CC and DD. Find the value of nn.

Solution

Answer: 13261326

Pick any contestant xx. Suppose he has played against y1,y2,,y100y_1, y_2, \dots, y_{100} (call these Group Y contestants). Denote the contestants who have not played against xx by z1,z2,,zmz_1, z_2, \dots, z_m (call these Group Z contestants).

Figure 1

A Group Y contestant (who has played against xx) has exactly 5050 common opponents with xx (who must be Group Y contestants), and so has played against exactly 100150=49100 - 1 - 50 = 49 Group Z contestants. On the other hand, since a Group Z contestant has not played against xx, he has exactly 44 common opponents with xx (who must be Group Y contestants). Thus the number of games between a Group Y contestant and a Group Z contestant is equal to 100×49100 \times 49 as well as 4m4m. It follows that these numbers are equal, and so
n=1+100+m=1+100+100×494=1326. n = 1 + 100 + m = 1 + 100 + \frac{100 \times 49}{4} = 1326.
The scenario described in the question is indeed possible. Note that the answer is actually (522)\binom{52}{2}. To construct the scenario, label the contestants by 22-element subsets of {1,2,,52}\{1, 2, \dots, 52\}, and let two contestants play a game if and only if their corresponding subsets have a common element. It is easy to check that all given conditions are satisfied.

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.