Competition problem — Combinatorics

Library / /6 of 16

Combinatorics Difficulty 6.2 National olympiad Find the answer Argentina

Eight teams take part in a rugby tournament in which every team plays exactly one match against each of the other seven teams. In each match, if the teams draw against each other, both of them earn 1 point; otherwise, the winner earns 2 points and the loser earns no points.
At the end of the tournament, the final scores of the eight teams are all different and the score of the winning team equals the sum of the four lowest scores. Give an example of a tournament which satisfies all these conditions.

Your answer

A number or a short expression. Spacing and $ signs are ignored.

Solution

We represent the tournament as a table that in the cell $(i, j)$ contains the number of points earned by team $i$ in the match versus team $j$ . Consider the following tournament, where for every $1 \le i \le 8$ team $i$ defeats team $j$ for every $j > i$ .

| Team | T1 | T2 | T3 | T4 | T5 | T6 | T7 | T8 | Total |
|------|----|----|----|----|----|----|----|----|-------|
| T1 | - | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 14 |
| T2 | 0 | - | 2 | 2 | 2 | 2 | 2 | 2 | 12 |
| T3 | 0 | 0 | - | 2 | 2 | 2 | 2 | 2 | 10 |
| T4 | 0 | 0 | 0 | - | 2 | 2 | 2 | 2 | 8 |
| T5 | 0 | 0 | 0 | 0 | - | 2 | 2 | 2 | 6 |
| T6 | 0 | 0 | 0 | 0 | 0 | - | 2 | 2 | 4 |
| T7 | 0 | 0 | 0 | 0 | 0 | 0 | - | 2 | 2 |
| T8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | - | 0 |

Despite this example is not a solution, we can observe that the four lowest scores add up to $12$ , which is close to $14$ , the score of the winning team. If we change this tournament a bit by making team $1$ and team $8$ draw against each other, we will get a tournament that does satisfy all the conditions.

| Team | T1 | T2 | T3 | T4 | T5 | T6 | T7 | T8 | Total |
|------|----|----|----|----|----|----|----|----|-------|
| T1 | - | 2 | 2 | 2 | 2 | 2 | 2 | 1 | 13 |
| T2 | 0 | - | 2 | 2 | 2 | 2 | 2 | 2 | 12 |
| T3 | 0 | 0 | - | 2 | 2 | 2 | 2 | 2 | 10 |
| T4 | 0 | 0 | 0 | - | 2 | 2 | 2 | 2 | 8 |
| T5 | 0 | 0 | 0 | 0 | - | 2 | 2 | 2 | 6 |
| T6 | 0 | 0 | 0 | 0 | 0 | - | 2 | 2 | 4 |
| T7 | 0 | 0 | 0 | 0 | 0 | 0 | - | 2 | 2 |
| T8 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | - | 1 |

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.