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$
  • 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 '14 at 8:03
  • $\begingroup$ Rolled back to require a unique score. $\endgroup$ – Ross Millikan Jun 5 '14 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 '14 at 4:46
  • $\begingroup$ @jmac: that is correct. We don't consider the order the games are played, just the final tournament table. $\endgroup$ – Ross Millikan Jun 5 '14 at 4:47
2
$\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$
  • $\begingroup$ Good work. I had convinced myself that you couldn't get enough total points with that few $16$s. $\endgroup$ – Ross Millikan Oct 23 '14 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$ – Warlord 099 Oct 23 '14 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$
  • $\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$ – Ross Millikan May 15 '14 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$
  • $\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$ – Ross Millikan May 15 '14 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$ – Ross Millikan May 15 '14 at 15:57
  • $\begingroup$ Ack! I have 21 teams? How did that happen? Back to the drawing board! $\endgroup$ – SQB May 16 '14 at 6:18
0
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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