2020 AMC 10B Problem 23

P21-25~6 minPrint

Basic Counting Transformations & Symmetry Map the objects to something easier to count Use an invariant, parity, or coloring argument

Square $ABCD$ in the coordinate plane has vertices at the points $A(1,1), B(-1,1), C(-1,-1),$ and $D(1,-1).$ Consider the following four transformations:

$\quad\bullet\qquad$ $L,$ a rotation of $90^{\circ}$ counterclockwise around the origin;

$\quad\bullet\qquad$ $R,$ a rotation of $90^{\circ}$ clockwise around the origin;

$\quad\bullet\qquad$ $H,$ a reflection across the $x$ -axis; and

$\quad\bullet\qquad$ $V,$ a reflection across the $y$ -axis.

Each of these transformations maps the squares onto itself, but the positions of the labeled vertices will change. For example, applying $R$ and then $V$ would send the vertex $A$ at $(1,1)$ to $(-1,-1)$ and would send the vertex $B$ at $(-1,1)$ to itself. How many sequences of $20$ transformations chosen from $\{L, R, H, V\}$ will send all of the labeled vertices back to their original positions? (For example, $R, R, V, H$ is one sequence of $4$ transformations that will send the vertices back to their original positions.)

Show solution without answering

Key insight

Each move sends corner A to a neighboring corner, so after 19 moves the square is exactly one move from home, and exactly one 20th move finishes.

Solution

1. Each move shifts $A$ to a neighboring corner. Check with $A$ at $(1,1)$ : $L$ sends it to $(-1,1)$ , $R$ to $(1,-1)$ , $H$ to $(1,-1)$ , $V$ to $(-1,1)$ . It never stays put and never jumps to the opposite corner, and the same holds from any corner.
2. Color the corners like a checkerboard. Call $(1,1)$ and $(-1,-1)$ "white" and the other two "black". Every move switches the color of $A$ 's corner. After an odd number of moves, $A$ is on black, so the square is certainly not back home.
3. Count the possible positions. A position of the labeled square is fixed by where $A$ is ( $4$ choices) and whether the labels read counterclockwise or clockwise ( $2$ choices), so there are $8$ positions. The $4$ with $A$ on a black corner are exactly the positions you get from the start by one single move: $L$ , $R$ , $H$ or $V$ .
4. After $19$ moves the square is in one of those $4$ positions. Each can be undone by exactly one move: $L$ is undone by $R$ , $R$ by $L$ , $H$ by $H$ , and $V$ by $V$ .
5. Count. Choose the first $19$ moves freely: $4^{19}$ ways. For each, exactly one $20$ th move brings everything home. So the number of sequences is
$4^{19} = (2^2)^{19} = 2^{38}.$

The answer is $\boxed{\textbf{(C)}\ 2^{38}}$ .

Why this works

To count move sequences that return to the start, fix all the moves except the last and ask how many last moves work. Here the checkerboard coloring shows that after an odd number of moves the square is always exactly one move from home, and the four moves come in undo-pairs, so exactly one last move works. The example $R, R, V, H$ fits: after $R, R, V$ the square is one move from home, and $H$ finishes it.

Concise solution

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

Track where the label $A$ sits. Each of $L$ , $R$ , $H$ , $V$ moves whichever label is at a corner to an adjacent corner (a $90^\circ$ rotation or a reflection across a coordinate axis never sends a corner to itself or to the opposite corner). Color the corners like a checkerboard: $(1,1)$ and $(-1,-1)$ are "even," $(-1,1)$ and $(1,-1)$ are "odd." Every move flips the parity of $A$ 's corner.

A configuration of the labeled square is determined by where $A$ is and whether the square is flipped over (reflected) or not: $4 \times 2 = 8$ configurations. After $19$ moves, $A$ is at an odd corner, so the square is in one of the $4$ configurations with $A$ adjacent to home. Those four are exactly the results of applying a single $L$ , $R$ , $H$ or $V$ to the original square, and each is undone by exactly one of the four moves ( $L$ by $R$ , $R$ by $L$ , $H$ by $H$ , $V$ by $V$ ).

Therefore any sequence of $19$ moves can be completed in exactly one way, and no sequence of $19$ moves ends at the identity (wrong parity). The count is
$4^{19} = 2^{38}.$

The answer is $\boxed{\textbf{(C)}\ 2^{38}}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
Introduction to Geometry, Chapter 16: The More Things Change. . . (§16.1, §16.2, §16.3, §16.4)
Intermediate Counting & Probability, Chapter 4: Constructive Counting and 1-1 Correspondences (§4.4, §4.5, §4.6)
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques