Question

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?

A dotted grid 8 cells wide and 3 cells tall, with a 1 written in each cell of the middle row.

$130$

$144$

$146$

$162$

$196$

Answer: C

Concepts:graph theory casework

Difficulty rating: 2370

Small Hint:

Each middle-row cell must touch exactly one toothpick; after the two turnaround columns are fixed, each interior cell’s toothpick is independently above or below it

Big Hint:

A loop crossing the middle uses all $8,$ the first $7,$ the last $7,$ or the middle $6$ columns; its interior columns independently bend above or below

Solution:

Each middle-row cell must touch exactly one toothpick. First consider loops that pass from one side of the middle strip to the other. The loop can span all $8$ columns, the first $7,$ the last $7,$ or the middle $6;$ a narrower span would leave an outer middle cell untouched.

Once the two ends are fixed, each interior middle cell independently has its one toothpick on its top or bottom side, and the rest of the non-self-intersecting loop is forced. The four cases therefore contribute $2^6,2^5,2^5,$ and $2^4$ loops. There are also exactly two loops that do not cross the middle strip: the horizontal rectangle running entirely along the top or entirely along the bottom. Hence the total is $2^6+2^5+2^5+2^4+2$ $=64+32+32+16+2$ $=146.$

Thus, the correct answer is C.

2024 AMC 12A Problem 22

Answer: C

Difficulty rating: 2370

Small Hint:

Big Hint:

Solution:

Problem 22 in Other Years