Maths Olympiad Prep

Library / /20 of 23

Combinatorics Difficulty 7.0 National olympiad, round 2 Prove it Ireland

Five teams play in a soccer competition where each team plays one match against each of the other four teams. A winning team gains 5 points and a losing team 0 points. For a 0-0 draw both teams gain 1 point, and for other draws (1-1, 2-2, etc.) both teams gain 2 points. At the end of the competition, we write down the total points for each team, and we find that they form five consecutive integers. What is the minimum number of goals scored?

Solutions — 2

Solution 1

Ten matches are played each one contributing either 2, 4 or 5 points. Hence the total number of points is between 20 and 50.
If the team scores are five consecutive integers, then the total number of points must be a multiple of 5. If the total number of points is 20, all teams will score 4 and if the total number of points is 50 all team totals will be multiples of 5. Neither of these possibilities satisfy the conditions. Therefore, we need to consider the following five cases:
1. scores are 3, 4, 5, 6, 7,
2. scores are 4, 5, 6, 7, 8,
3. scores are 5, 6, 7, 8, 9,
4. scores are 6, 7, 8, 9, 10,
5. scores are 7, 8, 9, 10, 11.

Case (a) Number of wins is odd. 3 wins yield 15 points and the other seven matches yield more than 10 points. The only possibility is one win, 8 0-0 draws and one score draw. But the team that wins must gain at least 3 points in the other matches. Hence this case is impossible.

Case (b) The number of wins is even and cannot be 4 as only three teams have a score of five or more and none have a score of 10. No wins means there are 5 score draws and 5 no score draws. The teams scoring 8 and 7 must be involved in 7 score draws to achieve these totals. Hence, the only possibility is 2 wins 2 score draws and 6 no score draws. The table

| | A | B | C | D | E | total |
|---|---|---|---|---|---|-------|
| A | | 5 | 1 | 1 | 1 | 8 |
| B | 0 | | 1 | 1 | 5 | 7 |
| C | 1 | 1 | | 2 | 2 | 6 |
| D | 1 | 1 | 2 | | 1 | 5 |
| E | 1 | 0 | 2 | 1 | | 4 |

realizes this possibility. The minimum number of goals in this case is 6.

Case (c) The number of wins is odd. No team has more than one win. If the number of wins is five, each team must win one match and all other matches are no score draws. A total of 9 is now impossible. If the number of wins is 3, there must be 3 score draws and 4 no score draws. At least 9 goals are scored in this scenario. If the number of wins is 1, there are 6 score draws and three no score draws. This gives at least 13 goals.

Case (d) Again we can calculate the number of wins (W), score draws (S) and no score draws (N) yielding 40 points. The four possibilities are (W, S, N) = (6, 1, 3) or (4, 4, 2) or (2, 7, 1) or (0, 10, 0). The minimum number of goals is W+2SW + 2S which in each case is bigger than 6.

Case (e) Calculating possible values of (W, S, N) we obtain (7, 2, 1), (5, 5, 0) giving more than 6 goals.
Thus the minimum number of goals scored in the tournament is 6.

Solution 2

If the five consecutive scores of the teams are a2,a1,a,a+1,a+2a - 2, a - 1, a, a + 1, a + 2, the total number of points is 5a5a. Each match contributes 5, 4 or 2 points to this total.
Let ww be the number of matches that did not end in a draw, d0d_0 the number of 0-0 draws and d1d_1 the number of draws with goals. The minimal possible number of goals scored is g=w+2d1g = w + 2d_1. The number of matches is (52)=10\binom{5}{2} = 10, so we obtain
w+d0+d1=105w+2d0+4d1=5a. w + d_0 + d_1 = 10 \\ 5w + 2d_0 + 4d_1 = 5a.

Eliminating d0d_0 from these equations we obtain 3w+2d1=5(a4)3w + 2d_1 = 5(a - 4). This equation implies 3w2d1(mod5)3w \equiv -2d_1 \pmod 5, hence wd1(mod5)w \equiv d_1 \pmod 5. None of w,d1w, d_1 and w+d1w+d_1 can exceed 10. Hence, d1=w+5td_1 = w+5t with 2t2-2 \le t \le 2. We obtain g=w+2d1=3w+10tg = w + 2d_1 = 3w + 10t.
* If t=2t = -2, we have w=d1+1010w = d_1 + 10 \le 10, hence w=10,d1=0w = 10, d_1 = 0 and g=10g = 10.
* If t=1t = -1, we have d1=w50d_1 = w - 5 \ge 0 and w+d1=2w510w + d_1 = 2w - 5 \le 10, hence 5w75 \le w \le 7. If w6w \ge 6, we have g=3w108g = 3w - 10 \ge 8. For w=5w = 5 we get g=5g = 5.
* If t=0t = 0, and w3w \ge 3 we have g=3w+10t9g = 3w + 10t \ge 9.
* If t1t \ge 1, we have g10g \ge 10.
Hence, there are only four cases in which g6g \le 6. They are all shown in the table below. The values of d0,ad_0, a and gg are obtained from the equations above.

| case | w | d₁ | d₀ | a | g |
|------|---|----|----|---|---|
| 1 | 0 | 0 | 10 | 4 | 0 |
| 2 | 1 | 1 | 8 | 5 | 3 |
| 3 | 5 | 0 | 5 | 7 | 5 |
| 4 | 2 | 2 | 6 | 6 | 6 |

Case 1. If d0=10d_0 = 10 all matches were no score draws, hence all teams scored 5 points contradicting the conditions.
Case 2. If a=5a = 5, the winning team achieved 7 points. But, if w=1w = 1 the team who has won one match cannot have lost any of their matches, hence would have scored at least 8 points.
Case 3. If a=7a = 7, the maximum number of points a team scored is 9, hence no team won two matches. As d1=0d_1 = 0, the top team can have scored at most 3 points from the matches it didn't win, hence cannot have got 9 points in total.
Case 4. This case is actually possible, as the following table shows.

| | A | B | C | D | E | total |
|---|---|---|---|---|---|-------|
| A | 5 | 1 | 1 | 1 | 1 | 8 |
| B | 0 | 1 | 1 | 1 | 5 | 7 |
| C | 1 | 1 | | 2 | 2 | 6 |
| D | 1 | 1 | 2 | | 1 | 5 |
| E | 1 | 0 | 2 | 1 | | 4 |

Therefore, the minimum number of goals scored is 6.

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.