5
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ Do you know the answer to this puzzle? In other words, is there a solution-wanted or is it a challenge? $\endgroup$
    – SQB
    May 15, 2014 at 8:03
  • $\begingroup$ Rolled back to require a unique score. $\endgroup$ Jun 5, 2014 at 3:15
  • $\begingroup$ When you say, "upsets ... defined as times a team with a lower total score beat a team with a higher total score" you mean the total score for the tournament, not total score at the time of the match, correct? $\endgroup$
    – jmac
    Jun 5, 2014 at 4:46
  • $\begingroup$ @jmac: that is correct. We don't consider the order the games are played, just the final tournament table. $\endgroup$ Jun 5, 2014 at 4:47

4 Answers 4

3
$\begingroup$

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.

enter image description here

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.

$\endgroup$
2
  • $\begingroup$ Good work. I had convinced myself that you couldn't get enough total points with that few $16$s. $\endgroup$ Oct 23, 2014 at 20:39
  • $\begingroup$ I figured as much. That is why I tried to find the first solution I could starting with the least number of 16s and working my way up. $\endgroup$ Oct 23, 2014 at 20:41
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I would accept zero as a square, after all $0=0^2$. It is used in the solution. Good thoughts, but you can't have $11$ teams with $16$ each. They play too many games among themselves and there will be too many losses accumulated. $\endgroup$ May 15, 2014 at 13:10
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ But you have 21 teams. You also can't have three teams with 1 and one with 0, as the zero team must have lost to all three with 1 and they all played each other. If you delete the team with zero, you violate the condition that one team has a unique score. This was the "solution" I was avoiding with that. $\endgroup$ May 15, 2014 at 14:38
  • $\begingroup$ Please go to this meta thread and register your request for MathJax. I agree that we should and want to drum up votes in support. Thanks. $\endgroup$ May 15, 2014 at 15:57
  • $\begingroup$ Ack! I have 21 teams? How did that happen? Back to the drawing board! $\endgroup$
    – SQB
    May 16, 2014 at 6:18
1
$\begingroup$
  • 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.

$\endgroup$
5
  • $\begingroup$ How did you figure out that there will be exactly 3 upsets ? $\endgroup$ Dec 3, 2021 at 21:17
  • $\begingroup$ @HemantAgarwal: In the last bullet I consider where the teams that scored $4$ got their points. There are not enough points for them unless they get three from higher scoring teams. Another way to get there is to say there was a tournament among the $4,1,0$ teams, of which there were $5$. There were $10$ games in the tournament, so $10$ points scored. The total score of those $5$ teams is $13$, so $3$ points came from outside and must have been upsets. $\endgroup$ Dec 3, 2021 at 23:06
  • $\begingroup$ If there are fewer than three upsets there are not enough points for the bottom teams. If there are more there are not enough points for the top teams. $\endgroup$ Dec 3, 2021 at 23:41
  • $\begingroup$ So, I understood why the teams that scored 4 points, 1 point and 0 points would together cause 3 upsets. But, I don't understand how you figured out that the teams that scored 9 points each caused 0 upsets . Please explain. $\endgroup$ Dec 4, 2021 at 6:52
  • $\begingroup$ @HemantAgarwal: you are right. We know there were three games with $4$s that were upsets and three with $16$s, but the $4$s could upset a $9$ and a $9$ upset a $16$ up to three times. Either I misremembered the puzzle or it was initially flawed. $\endgroup$ Dec 5, 2021 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.