Chess tournament with 3 winners

Question

$20$ chess players participate in a tournament where every player plays with each of the others only once. The first $3$ players will get a prize. There are $2$ points awarded to the winner, no points awarded to the losing player and if the game is drawn, each player receives $1$ point. What is the least number of points to guarantee that some player will be among the first three?

My approach is a bit simplistic: All possible pairs are $20C2 = 190$.

All possible points are $2 \times 190 = 380$ because for each pair, the total number of points is $2$ (either $2+0$ or $1+1$).

So the average number per player is $380/20 = 19$.

Therefore if someone gets $20$ points, he will be in the top $3$, right?

Answer 1

I get the same answer at Hagen von Eitzen, but via somewhat different reasoning.

Suppose I arrive late for the tournament, and the other players have already played each other, so that only my $19$ games remain to be played. All I need to do is edge out one of the top three from the current tally. How hard can that be?

Well, the worst-case scenario is if the current top three each beat all the other $16$ players, so that, regardless of how the $6$ points for the three games amongst themselves get distributed, they have a total of $3\cdot2\cdot16+6=102$ points (for an average of $34$ points). Furthermore, the worst thing that can happen to me is if any losses or ties I incur occur against one or more of the current top three.

Now if I score $36$ or more, the current top three's total goes to at most $104$, for an average of less than $36$. That means I've outscored at least one of them, which puts me in the top three. On the other hand, if I only score $35$, their total can go to $105$, which allows for a four-way tie, e.g., if all of us tied each other and beat everyone else. That does not guarantee me a top-three finish.

Answer 2

Consider 3 players A, B and C. Now A wins over B, B wins over C and C wins over A. All of them wins their remaining matches. So all three have 18 wins and 1 lost. In other words, each have 36 points. Since all other players have lost to A, B and C, none of the players can reach more than 32 points.

So if you reach 36 points you are for sure in top 3.

As mentioned above, if 3 other players than you reach 36 points, you can at maximum have 32 points (as you have lost to A, B, C). If you go above 32 point, it means that you start taking points from either A, B or C.

Now assume you play a draw with all three. That would bring you to 35 points and likewise them to 35. So there are now four persons with 35.

So 35 points is not enough to ensure that you are in top three as four players can reach that score.

Consequently the answer is 36 points.

Edit

Alternative way of explaining it.

Situation 1: A wins over B, B wins over C and C wins over A. All of them wins their remaining matches. Each of them have 18 wins and 1 lost, i.e. 36 points. No other player can get above 32 points as they've all lost to A, B and C.

Situation 2: A wins over B, B wins over C and C wins over A. A, B and C plays a draw with D. They all win their remaining matches. A, B and C have 17 wins, 1 draw and 1 lost, i.e. 35 points. Player D has 16 wins, 3 draws and 0 lost, i.e. 35 points.

So situation 2 is not enough to ensure top three as there are four players with 35 points.

Consequently the answer is 36 points.

Answer 3

A short proof - short because it doesnt go into case analysis:

36 is sufficient: A player can score at most 19 wins. We will count a draw as half a loss. If you score 36 points, then you have 1 loss (in reality this could be two half-losses, i.e. two draws). Assume three other players are equal or better than you, then the 4 of you collectively have 4 (or fewer) losses. However, the 4 of you played each other in 6 games, and among just those 6 games you must collectively have 6 losses. This is a contradiction.

36 is necessary: 4 players can each score 35 by: drawing among themselves (worth 3 pts) and then beating the other 16 players (worth 32 pts).