At a volleyball tournament, each team plays exactly once against each other team. Each game has a winning team, which gets $1$ point. The losing team gets $0$ points. Draws do not occur. In the nal ranking, only one team turns out to have the least number of points (so there is no shared last place). Moreover, each team, except for the team having the least number of points, lost exactly one game against a team that got less points in the final ranking. a) Prove that the number of teams cannot be equal to $6$. b) Show, by providing an example, that the number of teams could be equal to $7$.
Problem
Source: Dutch NMO 2014 p3
Tags: combinatorics, Tournament
John-Wick
07.09.2019 11:55
(a)Suppose that the number of teams is 6. We shall derive a contradic- tion. First remark that the number of games equals 6×5 = 15. Hence, the 2 total number of points also equals 15. Let team A be the (only) team with the lowest score. Team A has at most 1 point, because if team A had 2 or more points, then each of the other five teams would have at least 3 points, giving a total number of points that is at least 2+3+3+3+3+3 = 17. Each team on the second last place in the ranking has lost to team A, because this is the only team with a lower score. Hence, team A also has at least 1 point. We deduce that A has exactly 1 point and that there is exactly one team, say team B, in the second last place in the ranking. Team B has at least 2 points and the remaining four teams, teams C, D, E and F, each have at least 3 points. The six teams together have at least 1+2+3+3+3+3 = 15 points. If team B had more than 2 points, or if any of the teams C through F had more than 3 points, then the total number of points would be greater than 15, which is impossible. Hence, team B has exactly 2 points and teams C through F each have exactly 3 points. The four teams C through F each lost to a team having a lower score (team A or team B). Hence, together, team A and team B must have won at least 4 games. This contradicts the fact that together they have only 1 + 2 = 3 points (b)In the table below there is a possible outcome for 7 teams called A through G. In the row corresponding to a team, crosses indicate wins against other teams. Row 2, for example, indicates that team B won against teams C and D and obtained a total score of 2 points. Each team (except A) has indeed lost exactly one match against a team with a lower score. These matches are indicated in bold.
Attachments:
