AMC 10 Step by Step

2013 AMC 10A Problem 24

P21-25~10 minPrint

Central High School is competing against Northern High School in a backgammon match. Each school has three players, and the contest rules require that each player play two games against each of the other school's players. The match takes place in six rounds, with three games played simultaneously in each round. In how many different ways can the match be scheduled?

Log in to save your progress.
Show solution without answering

Key insight

Each round is one of 6 matchings, in two groups of 3. Either all six are used once, or one group is used twice.

Solution

Call Central's players A,B,CA, B, C and Northern's X,Y,ZX, Y, Z. Write a game as two letters, like AXAX.

  1. What a round looks like. A round has 33 games and 66 players, so every player plays exactly once. A round is a way to match A,B,CA, B, C with X,Y,ZX, Y, Z, one each. There are 3×2×1=63 \times 2 \times 1 = 6 ways to do that:
Group 1Group 2
AX,BY,CZAX, BY, CZAX,BZ,CYAX, BZ, CY
AY,BZ,CXAY, BZ, CXAY,BX,CZAY, BX, CZ
AZ,BX,CYAZ, BX, CYAZ,BY,CXAZ, BY, CX

2. Why two groups. The three matchings in Group 1 share no game, and together they contain all 99 games once. The same is true for Group 2. Also, any matching from Group 1 and any from Group 2 share exactly one game. (For example, the two top rows share AXAX.)
3. The rule for a schedule. Each of the 99 games is played exactly twice over the 66 rounds.
4. What that forces. Take any matching PP from Group 1 and any QQ from Group 2. They share one game. That game is played only in rounds that use PP or QQ (it is in no other matching). So
(times P is used)+(times Q is used)=2.(\text{times } P \text{ is used}) + (\text{times } Q \text{ is used}) = 2.
This holds for every PP in Group 1 and every QQ in Group 2. So all Group 1 matchings are used the same number of times, say aa, and all Group 2 matchings are used 2−a2 - a times.
5. Three possibilities.
- a=1a = 1: all 66 matchings are used once each. Put them in order: 6×5×4×3×2×1=7206 \times 5 \times 4 \times 3 \times 2 \times 1 = 720 ways.
- a=2a = 2: the three Group 1 matchings are each used twice, Group 2 not at all. Six rounds, made of three pairs of identical rounds: 7202×2×2=90\dfrac{720}{2 \times 2 \times 2} = 90 orders.
- a=0a = 0: the same with Group 2: 9090 orders.
6. Total. 720+90+90=900720 + 90 + 90 = 900.

The answer is (E) 900\boxed{\textbf{(E)}\ 900}.

Why this works

The key move is to stop thinking about single games and think about whole rounds. Once a round is one of just 66 matchings, the "each game twice" rule becomes a simple rule about how often each matching is used, and it has only three answers. Counting the orders of rounds is then ordinary arranging, dividing by 22 for each pair of identical rounds.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Call Central's players A,B,CA, B, C and Northern's X,Y,ZX, Y, Z. There are 99 possible games, each played twice, for 1818 games in 66 rounds of 33. Since 33 games use all 66 players, every player plays exactly once per round, so a round is a pairing: a way to match A,B,CA, B, C with X,Y,ZX, Y, Z. There are 3!=63! = 6 pairings.

Split them into two families. Family I: {AX,BY,CZ}\{AX, BY, CZ\}, {AY,BZ,CX}\{AY, BZ, CX\}, {AZ,BX,CY}\{AZ, BX, CY\}; any two of these share no game, and together they cover all 99 games once. Family II: the other three pairings {AX,BZ,CY}\{AX, BZ, CY\}, {AY,BX,CZ}\{AY, BX, CZ\}, {AZ,BY,CX}\{AZ, BY, CX\}, with the same property. Crucially, each game belongs to exactly one Family I pairing and exactly one Family II pairing.

A schedule is a sequence of 66 pairings in which every game appears exactly twice. If a game lies in pairing PP (Family I) and QQ (Family II), then (times PP is used) ++ (times QQ is used) =2= 2. Since every PP pairs with every QQ through some game, all three Family I pairings are used the same number of times aa, and all Family II pairings 2−a2 - a times.

  • a=1a = 1: each of the 66 pairings once, in any order: 6!=7206! = 720 schedules.
  • a=2a = 2: the three Family I pairings twice each: 6!2! 2! 2!=90\frac{6!}{2!\,2!\,2!} = 90.
  • a=0a = 0: the three Family II pairings twice each: 9090.

Total: 720+90+90=900720 + 90 + 90 = 900. The answer is (E) 900\boxed{\textbf{(E)}\ 900}.

Review in the AoPS books

Similar problems

Problem © Mathematical Association of America (MAA), American Mathematics Competitions. Reproduced for non-commercial educational use. Solution and commentary are original to this site.