Maths Olympiad Prep

Library / /39 of 46

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it Russia

Eight players participated in a chess tournament, and each pair of players have played exactly once. It appeared that if two players AA and BB played a draw then the resulting numbers of points of AA and BB are different. Find the greatest possible number of draws in this tournament. (Each win is worth 11 point, each draw is worth 12\frac{1}{2} points, and each lose is worth 00 points.) (S. Tokarev)

Solution

Answer: 2020.

We will estimate the number SS — the sum of the numbers of draws for all 88 chess players. This sum is exactly twice the number of draws in the tournament (since each draw is counted twice — for both players).

We will prove that S41S \le 41 — then the number of drawn games in the tournament does not exceed 2020, since it is an integer. This number is indeed the answer, since an example with 2020 draws exists (see Fig. 8; the players are denoted by the letters AA, BB, CC, DD, EE, FF, GG, and HH).

Note immediately that if two people did not lose to anyone, then they played a draw with each other and, according to the condition, have different numbers of points; the same is true if they did not win against anyone. It follows that there is at most one person with 77 draws and at most 22 people with 66 draws (such a person either did not lose to anyone or did not win against anyone). In addition, there are at most one person with 55 draws, all of whose two decisive games were both won or both lost. Note that all other players with 55 draws have 3123\frac{1}{2} points.

Suppose there is a person XX with 77 draws; then there cannot be other players with 55 draws, because they would have the same number of points as XX, and they would have played a draw with XX. Therefore, in this case, there are at most 22 people with 55 draws, and S7+26+25+34=41S \le 7 + 2 \cdot 6 + 2 \cdot 5 + 3 \cdot 4 = 41.

Now suppose there is no person with 77 draws. Estimate in this case the number of players with 55 draws and 3123\frac{1}{2} points. Each of them must have played with each other not in a draw; however, they have only 22 decisive games — so there are at most 33 of them, and in total, the number of players with 55 draws does not exceed 3+2=53 + 2 = 5. Therefore, in this case, S26+55+4=41S \le 2 \cdot 6 + 5 \cdot 5 + 4 = 41, as required.

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 and solution reproduced as published; topic and difficulty added by this site.