MOG 2015 Q4
A tournament has \(n\) contestants. Each contestant plays exactly one game against every other contestant. Explain why the total number of games is \(\tfrac{1}{2}n(n - 1)\).
In a particular chess tournament, every contestant is supposed to play exactly one game against every other contestant. However, contestant \(A\) withdrew from the tournament after playing only ten games, and contestant \(B\) withdrew after just one game.
A total of 55 games were played.
Did \(A\) and \(B\) play each other?
Mathematical Olympiad for Girls 2015, Question 4. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: (b) Yes, \(A\) and \(B\) did play each other.
Commentary
There are quite a lot of ways of counting the number of games! We give some examples.
We could consider each contestant in turn. The first contestant plays \(n - 1\) games (against every contestant other than themselves). For the second contestant we have already counted the game against the first contestant, so she plays \(n - 2\) other games. Continuing this reasoning, we find that the total number of games is\[(n - 1) + (n - 2) + \dots + 2 + 1.\]There are a good few ways of working out this sum.
One way is to compare the sum to its reverse. If we call the sum \(S\), then we have both\[\begin{aligned}(n - 1) + (n - 2) + \dots + 2 + 1 &= S,\\ \text{and } 1 + 2 + \dots + (n - 2) + (n - 1) &= S.\end{aligned}\]By adding corresponding terms, we get\[(n - 1 + 1) + (n - 2 + 2) + \dots + (2 + n - 2) + (1 + n - 1) = 2S.\]The left-hand side of this equation is a sum of \(n - 1\) bracketed terms, each of which is equal to \(n\), so the sum is equal to \(n(n - 1)\). Thus \(S = \tfrac{1}{2}n(n - 1)\).
Yet another way is more geometrical. The sum can be represented by a triangle of dots: one dot in the first row, two dots in a second, and so on. The diagram shows two such triangle fitted together to form a rectangle.

If there are \(n - 1\) rows of dots, the rectangle has \(n - 1\) rows and \(n\) columns, and hence contains \(n(n - 1)\) dots in total. But the original sum represents half of this rectangle, so the result follows.
On the other hand, you may know about arithmetic series in general. This is an arithmetic series with \(n - 1\) terms, first term 1 and common difference 1. Therefore the sum is\[\frac{n - 1}{2}[2 + (n - 2)] = \frac{1}{2}n(n - 1).\]Finally, we can go about it differently. Instead of forming a sum, we can look at the number of ways to pair the contestants. We need to be careful not to count pairs twice. This is the solution we present below.
Contestants never play themselves but do play all the other \(n - 1\) competitors. Therefore there are \(n(n - 1)\) pairs \((X, Y)\) such that \(X\) plays \(Y\), with the contestants named in that order.
The game in which \(X\) plays \(Y\) is the same as that in which \(Y\) plays \(X\) however, so naming the contestants in order means that each game is counted twice. Therefore the total number of games is \(\tfrac{1}{2}n(n - 1)\).
Commentary
We need to check whether it is possible to have a total of 55 games in the two cases: when \(A\) and \(B\) played each other, and when they didn’t.
One way to do this would be to count the number of games that don’t involve \(A\) or \(B\) and then to add in the number of games played by \(A\) and by \(B\). Another way would be to count the total number of games if \(A\) and \(B\) had played the whole tournament, and then to subtract the numbers of games missed by \(A\) and \(B\) because they withdrew early.
In each case, we know that the total number of games played is 55. We don’t know how many contestants there were at the start, so give this number a name (say \(m\)). We’ll get an equation involving \(m\) that we can then try to solve. We’ll also need to be careful to remember that \(A\) and \(B\) were scheduled to play each other, so we mustn’t count that game twice.
Suppose that there are \(m\) contestants other than \(A\) and \(B\). The number of games those \(m\) contestants played with each other is \(\tfrac{1}{2}m(m - 1)\).
There are an additional 10 games played by \(A\). If those include a game between \(A\) and \(B\), then there are no additional games played by \(B\), so the total number of games played is\[\frac{1}{2}m(m - 1) + 10 = 55.\]If \(B\) did not play \(A\) then there is one additional game played by \(B\), so the total number of games is\[\frac{1}{2}m(m - 1) + 10 + 1 = 55.\]In the first case, \(m(m - 1) = 90\), which is possible when \(m = 10\). In the second case, \(m(m - 1) = 88\). The last equation has no integer solutions, since \(m(m - 1) \le 72\) when \(m \le 9\) and \(m(m - 1) \ge 90\) when \(m \ge 10\).
Thus \(A\) and \(B\) did play each other.
Note
There were 12 contestants at the start of the tournament.
Solution © UK Mathematics Trust, from the MOG 2015 solutions.