Eight players participated in a chess tournament, and each pair of players have played exactly once. It appeared that if two players and played a draw then the resulting numbers of points of and are different. Find the greatest possible number of draws in this tournament. (Each win is worth point, each draw is worth points, and each lose is worth points.) (S. Tokarev)
Solution
Answer: .
We will estimate the number — the sum of the numbers of draws for all 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 — then the number of drawn games in the tournament does not exceed , since it is an integer. This number is indeed the answer, since an example with draws exists (see Fig. 8; the players are denoted by the letters , , , , , , , and ).
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 draws and at most people with 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 draws, all of whose two decisive games were both won or both lost. Note that all other players with draws have points.
Suppose there is a person with draws; then there cannot be other players with draws, because they would have the same number of points as , and they would have played a draw with . Therefore, in this case, there are at most people with draws, and .
Now suppose there is no person with draws. Estimate in this case the number of players with draws and points. Each of them must have played with each other not in a draw; however, they have only decisive games — so there are at most of them, and in total, the number of players with draws does not exceed . Therefore, in this case, , as required.