2024 AMC 10A Problem 25

P21-25~12 minPrint

Paths & Grids Basic Counting Map the objects to something easier to count Split into exhaustive cases and handle each

The figure below shows a dotted grid $8$ cells wide and $3$ cells tall consisting of $1''\times1''$ squares. Carl places $1$ -inch toothpicks along some of the sides of the squares to create a closed loop that does not intersect itself. The numbers in the cells indicate the number of sides of that square that are to be covered by toothpicks, and any number of toothpicks are allowed if no number is written. In how many ways can Carl place the toothpicks?

Show solution without answering

Key insight

An upright middle-row toothpick forces a full top-to-bottom line. A loop has exactly two such lines, and every other middle square picks top or bottom.

Solution

Number the middle-row squares $1$ to $8$ from the left. Each needs exactly one toothpick. The top row and bottom row have no rules.

Step 1: an upright toothpick in the middle row forces a whole column line.

Suppose the loop uses an upright (vertical) side of a middle square. That toothpick already counts as the one side for the middle square on each side of it.
At its top end, the loop must keep going. Turning left or right would run along the top of one of those middle squares and give it a second side. So the loop goes straight up, to the top edge of the grid.
For the same reason, at the bottom end it goes straight down to the bottom edge.
So every upright toothpick in the middle row is part of a full line from the bottom of the grid to the top. Call this a crossing. A crossing on the line between squares $j$ and $j + 1$ serves both of them. A crossing on the left edge serves only square $1$ , and one on the right edge serves only square $8$ .

Step 2: loops with no crossing. Then the loop never passes through the middle row, so it lies entirely in the top row or entirely in the bottom row. In a row one square tall, a loop is a long thin rectangle. Its long side along the middle row must cover the top (or bottom) of all $8$ middle squares, so it must be the full-width rectangle. That gives exactly $2$ loops: one around the whole top row, one around the whole bottom row.

Step 3: loops with crossings have exactly two.

The loop has to go down and come back up, so it has at least two crossings.
Between crossings, the loop travels inside the top row or inside the bottom row, which are only one square tall. A crossing blocks the whole height of those rows, so a path in the top row can only connect a crossing to the crossing right next to it.
With four or more crossings, the tops would join in pairs of neighbours and the bottoms would too, making two separate loops. So a single loop has exactly two crossings, and the loop stays between them.
Every middle square needs a toothpick, so no square may lie outside the two crossings. The left crossing must be on the left edge or the line after square $1$ ; the right crossing must be on the right edge or the line before square $8$ .

Step 4: count the loops with two crossings.

Look at the top part of the loop, which runs from the top of the left crossing to the top of the right crossing. Above each middle square it either stays on the top edge of the grid, or dips down to run along the top side of that middle square. (In a row one square tall it cannot turn back.)
The bottom part is the same: below each middle square it either stays on the bottom edge or rises to run along the bottom side of that square.
A square next to a crossing already has its toothpick, so neither path may touch it. Every other middle square needs exactly one toothpick: either the top path dips over it or the bottom path rises under it. That is $2$ choices per square, and the choices do not affect each other.
Count the free squares for the four possible positions of the crossings:

left crossing	right crossing	squares served by crossings	free squares	loops
left edge	right edge	$1, 8$	$6$	$2^6 = 64$
after square $1$	right edge	$1, 2, 8$	$5$	$2^5 = 32$
left edge	before square $8$	$1, 7, 8$	$5$	$2^5 = 32$
after square $1$	before square $8$	$1, 2, 7, 8$	$4$	$2^4 = 16$

That is $64 + 32 + 32 + 16 = 144$ loops.

Step 5: total. $144 + 2 = 146$ .

The answer is $\boxed{\textbf{(C)}\ 146}$ .

Why this works

The row of $1$ s is a strong rule: one upright toothpick there forces a whole line through the grid, and after that only simple two-way choices remain. So first work out the forced skeleton of the loop (where it crosses the middle row), then count the free choices, which multiply. Finally, remember the loops that avoid the special row altogether; forgetting them gives choice (B).

Concise solution

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

Number the middle-row cells $1$ to $8$ from the left; each needs exactly one toothpick.

A middle-row vertical forces a full column. If the loop uses the vertical side at column line $x = j$ of the middle row, that toothpick already serves the middle cell(s) beside it, so at its top end the loop cannot turn along their top sides: it must continue up to the top edge of the grid, and likewise down to the bottom edge. So every middle-row vertical is part of a full-height crossing, serving cells $j$ and $j+1$ (only cell $1$ if $j = 0$ , only cell $8$ if $j = 8$ ).

Exactly two crossings, or none. Crossing tops must be joined by paths inside the one-cell-tall top row, bottoms inside the bottom row. Such a path cannot get past another crossing, so a single simple loop uses exactly two crossings $j_1 < j_2$ and lies between them. Middle cells outside $[j_1, j_2]$ would get nothing, so $j_1 \in \{0, 1\}$ and $j_2 \in \{7, 8\}$ .

Count. The top path runs rightward from $(j_1, 3)$ to $(j_2, 3)$ ; over each cell it stays on the top edge or dips to the middle row's top side. The bottom path stays on the bottom edge or rises to the middle row's bottom side. Cells served by a crossing must be avoided by both; every other middle cell needs exactly one of "top dips" or "bottom rises", an independent binary choice. Free cells number $6, 5, 5, 4$ for $(j_1, j_2) = (0,8), (1,8), (0,7), (1,7)$ : $64 + 32 + 32 + 16 = 144$ .

With no crossings the loop is a $1$ -tall rectangle inside the top or bottom row that must cover all eight middle cells: $2$ more loops.

Total $144 + 2 = 146$ . The answer is $\boxed{\textbf{(C)}\ 146}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 5: More With Combinations (§5.2)
Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.2)
Intermediate Counting & Probability, Chapter 4: Constructive Counting and 1-1 Correspondences (§4.4, §4.5, §4.6)