2024 AMC 12A Problems/Problem 20

The following problem is from both the 2024 AMC 12A #20 and 2024 AMC 10A #23, so both problems redirect to this page.

Problem

The figure below shows a dotted grid $8$ cells wide and $3$ cells tall consisting of $1^{\prime\prime} \times 1^{\prime\prime}$ 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?

$[asy] size(6cm); for (int i=0; i<9; ++i) { draw((i,0)--(i,3),dotted); } for (int i=0; i<4; ++i){ draw((0,i)--(8,i),dotted); } for (int i=0; i<8; ++i) { for (int j=0; j<3; ++j) { if (j==1) { label("1",(i+0.5,1.5)); }}} [/asy]$

$\textbf{(A)}~130\qquad\textbf{(B)}~144\qquad\textbf{(C)}~146\qquad\textbf{(D)}~162\qquad\textbf{(E)}~196$

(Best) Solution 1

There are two possibilities for the loop if it does not cross the middle row of $1$ 's: a $1\times 8$ rectangle around the top row of cells or a $1\times 8$ rectangle around the bottom row of cells. Otherwise, notice that wherever the loop crosses this middle row, it proceed straight in both directions after the middle row. This divides the dotted grid into two components, and both ends of the loop must enter the same connected component. It follows that the loop must cross one of the leftmost two columns and one of the rightmost two columns for four configurations total. $[asy] unitsize(1.1cm); defaultpen(linewidth(0.7)+linetype("1 4")); void cross(pair P) { real r = 0.1; draw((P.x-r,P.y-r)--(P.x+r,P.y+r)^^(P.x+r,P.y-r)--(P.x-r,P.y+r),linewidth(1)+solid); } for(int i=0;i<=3;i=i+1) { draw((0,i)--(2.5,i)); } for(int j=0;j<=1;j=j+1) { draw((j,0)--(j,3)); label("$1$",(j+0.5,1.5),fontsize(15)); } draw((2,0)--(2,3)); cross((0.5,1)); cross((1,1.5)); cross((0.5,2)); draw((1,0)--(0,0)--(0,3)--(1,3),linewidth(1.4)+solid); real s=4; for(int i=0;i<=3;i=i+1) { draw((s,i)--(s+2.5,i)); } for(int j=0;j<=1;j=j+1) { draw((s+j,0)--(s+j,3)); label("$1$",(s+j+0.5,1.5),fontsize(15)); } draw((s+2,0)--(s+2,3)); cross((s+0.5,1)); cross((s,1.5)); cross((s+0.5,2)); cross((s+1.5,1)); cross((s+2,1.5)); cross((s+1.5,2)); draw((s+2,0)--(s+1,0)--(s+1,3)--(s+2,3),linewidth(1.4)+solid); [/asy]$ In each case, there are two ends of the loop that must connect -- one across the top and one across the bottom -- along with some number of $1$ 's in the middle of the grid. Suppose there are $n$ such $1$ s. For each $1$ , the loop can cover either the top edge or the bottom edge. These choices are independent of each other, and so the number of ways to connect both ends of the loop is $2^n$ . The figure below shows one possibility when $n = 6$ . $[asy] unitsize(1.1cm); defaultpen(linewidth(0.7)+linetype("1 4")); void cross(pair P) { real r = 0.1; draw((P.x-r,P.y-r)--(P.x+r,P.y+r)^^(P.x+r,P.y-r)--(P.x-r,P.y+r),linewidth(1)+solid); } for(int i=0;i<=3;i=i+1) { draw((0.5,i)--(7.5,i)); } for(int j=1;j<=6;j=j+1) { draw((j,0)--(j,3)); label("$1$",(j+0.5,1.5),fontsize(15)); cross((j,1.5)); } draw((7,0)--(7,3)); cross((7,1.5)); draw((1,2)--(2,2)^^(2,1)--(4,1)^^(4,2)--(5,2)^^(5,1)--(6,1)^^(6,2)--(7,2),linewidth(1.4) + solid + red); draw((0.5,3)--(1,3)--(1,2)^^(2,2)--(2,3)--(4,3)--(4,2)^^(5,2)--(5,3)--(6,3)--(6,2)^^(7,2)--(7,3)--(7.5,3),linewidth(1.4)+solid); draw((0.5,0)--(2,0)--(2,1)^^(4,1)--(4,0)--(5,0)--(5,1)^^(6,1)--(6,0)--(7.5,0),linewidth(1.4)+solid); [/asy]$ Returning to the original problem, of the four possibilities, one gives $n = 6$ , two give $n = 5$ , and one gives $n = 4$ . Remembering to add back the $2$ , it follows that the total number of solutions is $2^6 + 2\cdot 2^5 + 2^4 + 2 = 64 + 64 + 16 + 2 = \boxed{\textbf{(C)}~146}.$

~djmathman

Solution 2 (Cheese)

Notice that for any case where the closed loop does not connect from the top side of the ones and bottom side of the ones, there are two of these cases. A cheese solution can be found from this; noting that B and C are the only two options to each other, and, being two apart, with people likely to forget this case, $\boxed{\textbf{(C) }146}$ is likely to be the correct answer. Cheese solution done by juwushu.

Solution 3 (Observation)

We have $2$ cases where the loop does not go through the middle.

If the loop goes through the middle, we must have a full column on $(0,8),(0,7),(1,8),(1,7).$ Then we have $6,5,5,4$ empty middle squares. For each one we can have one on top or one on bottom, so $2^6+2^5+2^5+2^4=144.$ Notice that for each case of fixed toothpicks, there is only one way to form the loop. Then we just add $2+144=\boxed{\textbf{(C) } 146.}$

~nevergonnagiveup

Video Solution by Power Solve

https://www.youtube.com/watch?v=FRNbJ5wIGRo

Video Solution By SpreadTheMathLove

https://www.youtube.com/watch?v=huMQ9J7rIj0&t=77s

2024 AMC 12A (Problems • Answer Key • Resources)
Preceded by Problem 19	Followed by Problem 21
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

2024 AMC 10A (Problems • Answer Key • Resources)
Preceded by Problem 22	Followed by Problem 24
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions

Page

Toolbox

Search