Round-Robin Tournament

Question

20 teams played in a round-robin tournament.
The winner of each game got 1 point, and the loser got 0; there were no draws.
Each team's total score was a square number.
At least one team had a unique score.

How many upsets were there, defined as times a team with a lower total score beat a team with a higher total score?

_{Source: New Scientist  Enigma column, long ago.}

Answer 1

I just came across this problem and I just wanted to point out that although the original poster posted a solution to the problem, there is more than one possible solution. I came up with a solution that has 1 1-win team (the unique score), 2 4-win teams, 13 9-win teams, and 4 16-win teams. Below is a representation of all of the games that were played. The 'W' or 'L' is in relation to the team on the left's outcome against the team listed above.

The yellow indicates games where upsets occurred. This particular solution had 13 upsets.

EDIT: I might also point out that this is only one possible way that the games could have played out in this scenario. If they games were played differently there might be more or less upsets.

Answer 2

To solve this puzzle you first have to know the boundaries in whose you are working.

There are 20 teams, a total of 190 matches (and 190 points).

You have to divide the 190 points to all teams. The points you have to distribute are 0, 1, 4, 9 and 16 since a team can't get more than 19 points.

So first we go to the team with 0 points. This can only be one because all the other teams have at least 1 win against this team. The second team then has 1 point. Again all other teams now have at least 2 points so the next few teams can have at least 4 points. If we follow this in the end I got 4 teams with 4, 5 teams with 9, 6 teams with 16 2 with 10 and 1 with 12. To fix those few teams with an non square number, we either have to get them to 16 or to 9. when we get them all to 9 we can get a 4 to 9 too (5 points in total).

So the result then is the following:

1 team with 0 points
1 team with 1 points
3 team with 4 points
9 team with 9 points
6 team with 16 points

This is the way I can solve this puzzle, maybe there is a mathematical way I don't know of.

Answer 3

Within a group of $n$ teams, there are $\frac{n (n - 1)}{2}$ points to share. But that goes for each subgroup as well. A subgroup of m teams, where $m < n$, will have $\frac{m (m - 1)}{2}$ points between them, plus (at most) $m (n - m)$ points from the teams outside the subgroup. If we want to give this group the same number of points ($x$), that total is equal to $m \cdot x$. So $$\begin{align} m \cdot x & \le m \cdot \frac{m - 1}{2} + m \cdot (n - m) \\ x & \le \frac{m - 1}{2} + (n - m) \\ x & \le n - \frac{m - 1}{2} \end{align}$$
Plugging in the numbers, we get that we can have at the most 7 teams with 16 points. That leaves us with 13 teams and 78 points between them.

Applying the same principle again and again, we end up with

7 teams scored 16 points
7 teams scored 9 points
3 teams scored 4 points
3 teams scored 1 point
1 team scored 0 points

Answer 4

• We know there are $190$ points distributed among the teams, and the allowable scores are $16,9,4,1,0$.
• You can't have more than $7$ teams with $16$ because they would have to lose too many games in the round robin among themselves.
• You can have $ 7 \cdot 16, 7 \cdot 9, 3 \cdot 4, 3 \cdot 1$, but there is no team with a unique score.
• You can also have $ 6 \cdot 16, 9 \cdot 9, 3 \cdot 4, 1 \cdot 1, 1 \cdot 0$. In that case the three teams that scored $4$ got two points each from the $0,1$ teams and an average of $1$ in their round robin, so they need three more points (which came at the expense of the $16$'s).

There were three upsets.