AMC 10 · 2021 · #22

Grade 11 counting

Archetype Overlap / Complement Counting └ Sub-archetype Complement by Subtracting Forbidden Arrangements

combinations-basiccomplementary-countingcaseworkfundamental-counting-principle caseworkcomplementary-counting ↑ Prerequisites: combinations-basic

📏 Long solution 💡 3 insights

Problem

Two players fill a three by three board, one placing first and the two alternating. The game stops the moment someone gets three of their own symbols in a line — horizontal, vertical, or diagonal — or when all nine boxes are full. The second player won on their third symbol. Count how many different final boards are possible.

Pick an answer.

(A)

(B)

112

(C)

120

(D)

148

(E)

160

How to solve

Strategy Make a Systematic List

Tool #11 (Work Backwards) — we are handed the ending, so read the ending backwards to learn exactly what the final board must look like: 3 O's forming a line, 3 X's forming no line. Tool #2 (Systematic List) — "how many ways" over a small board; list the 8 winning lines and count X-placements for each. Tool #7 (Subproblems) — the 8 lines do not all behave alike, so split into row/column lines and diagonal lines. Tool #1 (Diagram) — sketch the six leftover boxes for each case and see which lines still fit inside them. Tool #16 (Complement) — for each O-line, count all X-placements first and subtract the few that accidentally make an X line.

1STEP 1

Read the ending backwards

Read the ending backwards.

final board = 3 X + 3 O + 3 empty, O in a line, X not in a line

2STEP 2

List the eight winning lines

There are eight winning lines.

3 + 3 + 2 = 8 lines; 9 - 3 = 6 boxes left

3STEP 3

Count X-placements before filtering

Count the placements before filtering.

C(6, 3) = (6 · 5 · 4)/(3 · 2 · 1) = 20

4STEP 4

Case 1: O sits on a row or column

For a row or column, subtract the leftover lines.

6 × (20 - 2) = 6 × 18 = 108

5STEP 5

Case 2: O sits on a diagonal

For a diagonal there is nothing to subtract.

2 × 20 = 40

6STEP 6

Add the two cases

Adding the two cases gives 148.

108 + 40 = 148

Answer

148

Upper bound first: if we ignored the "X's must not line up" rule we would get 8 × 20 = 160, which is exactly choice (E) — the trap answer for anyone who forgets that Azar would already have won. Our answer must be a little under that, and 148 is 12 less, which is small and believable since only a handful of X-placements accidentally form a line. It also sits above (C) 120, so choices (A), (B), and (C) are all too small to be reachable by shaving only a few boards off 160. Choice (D) 148 fits.

💡Key takeaway

The ending of the game tells you the whole board: 3 O's on a line, 3 X's not on a line — so count C(6, 3) = 20 X-placements for each of the 8 O-lines, drop the 2 bad ones whenever the O's sit on a row or column, and get 6 × 18 + 2 × 20 = 148.

Read the ending backwards
List the eight winning lines
Count X-placements before filtering
Case 1: O sits on a row or column
Case 2: O sits on a diagonal
Add the two cases