51st Ukrainian National Mathematical Olympiad, 3rd Round

Question

In volleyball tournament there are 8 teams, that play one-round tournament (each team plays exactly one game with another). Each win worth 1 point, each lose worth 0 points, there are no draws in volleyball. After tournament is finished, if the difference between the first and the second place, does not exceed 1 point, then they play one extra game. The same applies for the teams that scored 3-d and 4-th, 5-th and 6-th, and 7-th and 8-th respectively. What is the least number of extra games can occur?

Note. After tournament is finished each place takes only one team, even though two teams can have the same number of points.

Accepted Answer

If we assume, that there were no extra games then the difference between 1-st and 2-nd, 3-d and 4-th, 5-th and 6-th, and 7-th and 8-th is at least 2 points and therefore the difference between 1-st and 8-th places is at least 8 points, while the first place can not have more than 7 points. The following example shows that 1 extra game is indeed possible: | Team | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | Points | |-----------|---|---|---|---|---|---|---|---|--------| | 1 place | XX| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 7 | | 2 place | 0 | XX| 0 | 1 | 1 | 1 | 1 | 1 | 5 | | 3 place | 0 | 1 | XX| 0 | 0 | 1 | 1 | 1 | 4 | | 4 place | 0 | 0 | 1 | XX| 1 | 0 | 1 | 1 | 4 | | 5 place | 0 | 0 | 1 | 0 | XX| 1 | 1 | 1 | 4 | | 6 place | 0 | 0 | 0 | 1 | 0 | XX| 0 | 1 | 2 | | 7 place | 0 | 0 | 0 | 0 | 0 | 1 | XX| 1 | 2 | |…

Team	1	2	3	4	5	6	7	8	Points
1 place	XX	1	1	1	1	1	1	1	7
2 place	0	XX	0	1	1	1	1	1	5
3 place	0	1	XX	0	0	1	1	1	4
4 place	0	0	1	XX	1	0	1	1	4
5 place	0	0	1	0	XX	1	1	1	4
6 place	0	0	0	1	0	XX	0	1	2
7 place	0	0	0	0	0	1	XX	1	2
8 place	0	0	0	0	0	0	0	XX	0