In a chess tournament, each of the six players will play with every other player exactly once. What is the number of matches that will be played during the tournament ?

Correct — B, (b) 15.

THE INSIGHT THAT UNLOCKS THIS ITEM is that a match is a PAIR of players, not a player. So the question is not 'how many games does each person play' but 'how many different pairs can be formed from six people', and the answer is the number of ways of choosing 2 out of 6.

6C2 = (6 x 5) / (2 x 1) = 30/2 = 15

THE SAME ANSWER WITHOUT THE FORMULA, which is worth having because it explains where the division by two comes from. Each of the six players meets the other five, so if we simply add up the games from every player's point of view we get

6 players x 5 opponents each = 30

But that 30 counts every match TWICE — once as a game of the player and once as a game of the opponent, since a single match between A and B appears in A's five and again in B's five. Halving corrects the double count:

30 / 2 = 15

THE SAME ANSWER A THIRD WAY, by counting each match once at the moment it is first available. The first player has five opponents she has not yet met, so five matches. The second player has already met the first, so four new ones. The third has four new... and so on:

5 + 4 + 3 + 2 + 1 = 15

That is a TRIANGULAR NUMBER, and the general result n(n-1)/2 is the same triangular formula. It is worth recognising because so many counting problems reduce to it.

A CROSS-CHECK FROM THE STRUCTURE OF A TOURNAMENT, which is the most convincing of all. With an even number of players, a round-robin can be scheduled so that every player is occupied in every round. Six players make three matches per round, and each player needs five rounds to meet five opponents. So

3 matches per round x 5 rounds = 15 matches

Three independent routes give the same number, which is as much confirmation as an examination answer needs.

WHY NO ANSWER ABOVE 15 IS POSSIBLE AT ALL, and this argument alone removes two of the four options before any calculation. The total number of 'games played' summed over all six players is fixed at 6 x 5 = 30, and every match contributes exactly 2 to that total, one for each participant. So the number of matches must be exactly 30/2 = 15. Anything larger would require some pair of players to meet more than once, which the stem forbids with the words 'exactly once'.

THE GENERAL RESULTS WORTH CARRYING AWAY. For n players each meeting every other exactly once, the number of matches is n(n-1)/2. If they meet twice — a double round-robin, home and away — it is n(n-1). This is the same count as the HANDSHAKE PROBLEM, as the number of line segments joining n points with no three in a line, and as the number of links in a fully connected mesh network of n computers. One formula, many disguises.

The options are printed as bare numerals, and the stem carries a space before its question mark, as this booklet sets them.

Why the others are wrong

• (a)10 — Ten is the answer to the same question asked about FIVE players rather than six: 5 x 4 / 2 = 10. It is therefore the option for a candidate who has the method exactly right and the count wrong — most often by taking the 'five opponents' that each player faces as though it were the number of players, or by dropping one competitor while listing them out. It is also the fourth triangular number, 4 + 3 + 2 + 1, which is what the successive-differences count gives if it is started one step too late. The error is worth naming precisely because the method is sound: the candidate has understood that matches are pairs and that pairs must not be double counted, and has then applied it to the wrong n. The guard against it is to write the formula with the symbol first, n(n-1)/2, and substitute only afterwards, so that the six of the stem and the five opponents it implies cannot change places. Checking the result against the tournament structure catches it too: six players cannot play a five-round schedule of three matches a round and produce only ten games.
• (c)20 — Twenty is above the ceiling this problem has, and the ceiling argument disposes of it without any arithmetic about where the number might have come from. Summed over all six players, the total count of games played is fixed at 6 x 5 = 30, and each match contributes exactly two to that total, so the number of matches cannot be anything other than 15. To reach twenty, at least some pairs would have to meet more than once, and the stem says 'exactly once'. Where the number does come from, if a candidate is looking for the misstep it represents, is choosing the wrong group size: 6C3 — the number of ways of picking three players out of six — is 20. A match involves two players, not three, so the wrong quantity has been counted. Getting into the habit of asking 'how many people does one unit of the thing I am counting involve' fixes the choose-two against choose-three confusion in every problem of this family.
• (d)25 — Twenty-five is the square of five, and it is what a candidate produces by multiplying the five opponents of one player by five again, or by reasoning loosely that 'roughly five each for five or six players' must mean something in the twenties. Neither route is valid, and like the previous option it falls to the ceiling argument at once: the sum of games over all players is 6 x 5 = 30, each match is counted twice in that sum, so there are exactly 15 matches and no arrangement satisfying the stem can produce more. A tournament that genuinely yields 25 matches would be one between two teams of five in which every member of one team plays every member of the other — a quite different structure, in which the two sides are distinguished and no player meets a team-mate. Recognising which structure a problem has is the real skill here: everyone against everyone within one group gives n(n-1)/2, while everyone in one group against everyone in another gives the product of the two group sizes.

THE HANDSHAKE PROBLEM is one of the small number of counting results that repay being learned once and recognised thereafter. If n people each shake hands with every other exactly once, or n players each meet every other exactly once, the number of handshakes or matches is

nC2 = n(n-1)/2

WHY THE FORMULA LOOKS LIKE THAT. There are n choices for the first member of a pair and n-1 for the second, giving n(n-1) ORDERED pairs. But a match between A and B is the same match as one between B and A, so each unordered pair has been counted twice, and dividing by two corrects it. That division is the entire content of the formula and the entire content of the commonest error.

PERMUTATION AND COMBINATION, which is what the division distinguishes. A PERMUTATION counts arrangements in which order matters: nPr = n! / (n-r)! A COMBINATION counts selections in which order does not matter: nCr = n! / [ r! (n-r)! ] The relation between them is nCr = nPr / r!, the r! being the number of ways of ordering a chosen group. Ask of every counting problem whether swapping two chosen items produces a different outcome. If it does, count permutations; if it does not, count combinations. A match, a handshake, a committee and a line joining two points are all unordered; a first-and-second placing, a code and a seating are ordered.

TRIANGULAR NUMBERS. The values of n(n-1)/2 for n = 2, 3, 4, 5, 6, 7 are 1, 3, 6, 10, 15, 21, and each is the sum of the first n-1 whole numbers. Recognising 15 as 1+2+3+4+5 is often faster than computing the formula, and knowing the sequence lets a candidate check an answer instantly.

USEFUL VALUES OF nC2, worth memorising as far as ten: 6C2 = 15, 7C2 = 21, 8C2 = 28, 9C2 = 36, 10C2 = 45.

THE SAME COUNT IN OTHER CLOTHES. All of these are nC2: handshakes among n people; matches in a single round-robin among n players; line segments joining n points with no three collinear; links in a fully connected mesh network of n computers; chords of a circle through n marked points. And two close relatives that are NOT the same count: the number of DIAGONALS of an n-sided polygon is n(n-1)/2 minus the n sides; the number of matches in a DOUBLE round-robin, in which each pair meets twice, is n(n-1) with no halving.

ROUND-ROBIN SCHEDULING, which supplies the cross-check. With n players and n even, a schedule exists with n-1 rounds and n/2 matches in each round, every player playing in every round. Six players therefore give five rounds of three matches, and 5 x 3 = 15. With n odd, one player sits out each round and there are n rounds of (n-1)/2 matches.

KNOCKOUT TOURNAMENTS ARE THE OTHER STRUCTURE and are counted quite differently: to reduce n entrants to one winner, every match eliminates exactly one player, so n-1 matches are required regardless of how the draw is arranged. Six players in a knockout need five matches, not fifteen. Reading which structure the stem describes — every player against every other, or elimination — is the first thing to settle in any tournament problem.

Key facts

• In a single round-robin where n players each meet every other exactly once, the number of matches is nC2 = n(n-1)/2.
• For six players this is 6 x 5 / 2 = 15.
• The division by two corrects the double count: adding up matches from each player's point of view counts every match twice.
• The same total can be reached as 5 + 4 + 3 + 2 + 1, a triangular number.
• A round-robin among six players can be scheduled as five rounds of three matches each, giving 15.
• In a double round-robin, where each pair meets twice, the count is n(n-1) with no halving.
• A knockout tournament of n entrants needs exactly n-1 matches, since every match eliminates one player.
• A permutation counts ordered arrangements, nPr = n!/(n-r)!; a combination counts unordered selections, nCr = n!/[r!(n-r)!]; and nCr = nPr / r!.
• The same nC2 count gives handshakes among n people, line segments joining n points with no three collinear, and links in a fully connected mesh network of n computers.
• The number of diagonals of an n-sided polygon is n(n-1)/2 minus n, because the sides must be removed.

Common traps

• Forgetting to halve. Counting matches from each player's point of view double counts every match, and 6 x 5 = 30 is that uncorrected total.
• Using the number of opponents in place of the number of players. Six players give five opponents each, and substituting five for n produces 10.
• Choosing the wrong group size, as in computing 6C3 for a contest that involves two players.
• Treating a round-robin as a knockout or the reverse. Six players give 15 matches in a round-robin but only 5 in a knockout.
• Halving twice, by applying the formula and then dividing again out of caution.
• Missing an explicit 'exactly once' or 'twice' in the stem, which is the difference between n(n-1)/2 and n(n-1).

• practice — not a real PYQ

  Eight teams take part in a league in which every team plays every other team exactly twice. What is the total number of matches played ?

  • (a)28
  • (b)36
  • (c)56
  • (d)64

  Answer(c) 56 — a single round-robin among eight teams gives 8 x 7 / 2 = 28 matches, and because every pair meets twice the total is 8 x 7 = 56. The figure 28 is the single round-robin count and is the trap for a candidate who overlooks the word 'twice', while 64 is 8 squared and would count a team as playing itself.

• practice — not a real PYQ

  Twelve players enter a knockout tournament in which every match eliminates the loser and a single champion emerges. What is the least number of matches that must be played ?

  • (a)6
  • (b)11
  • (c)12
  • (d)66

  Answer(b) 11 — each match removes exactly one player, and eleven of the twelve must be removed to leave one champion, so eleven matches are needed however the draw is arranged. The figure 66 is the round-robin count 12 x 11 / 2 and belongs to a quite different structure, while 6 is only the first round.