Difference between revisions of "2020 AMC 10B Problems/Problem 23"

m (Solution 6 (Quick))
m (Solution 7 (Group Theory))
Line 114: Line 114:
  
 
~Arcticturn
 
~Arcticturn
 
== Solution 7 (Group Theory) ==
 
 
This problem is a [https://en.wikipedia.org/wiki/Dihedral_group Dihedral Group] problem, <math>D_4</math>, in [https://en.wikipedia.org/wiki/Group_theory Group Theory].
 
 
The transformation has associativity, for <math>x, y, z \in \{ L, R, H, V \}</math>, <math>(x \circ y) \circ z = x \circ (y \circ z)</math>
 
 
Let <math>I</math> be the initial state of the square <math>A(1,1), B(-1,1), C(-1,-1),</math> and <math>D(1,-1)</math>.
 
 
<cmath>\begin{align}
 
R \circ L = L \circ R = V \circ V = H \circ H = I\
 
V \circ H = R \circ R = H \circ V = L \circ L\
 
H \circ R = L \circ H = V \circ L = R \circ V\
 
V \circ R = L \circ V = H \circ L = R \circ H
 
\end{align}</cmath>
 
 
It's not hard to see that after a series of transformations from initial state <math>I</math> to initial state <math>I</math>, the number of transformations must be even. Denote <math>f(2n)</math> be the number of sequences of <math>2n</math> transformations from initial state <math>I</math> to initial state <math>I</math>. We are going to prove <math>f(2n) = 4^{2n-1}</math>
 
 
For each transformation composite operator, there are <math>4</math> replacements.
 
 
For example, when <math>n = 2</math>:
 
 
<math>R \circ R \circ R \circ R = (R \circ R) \circ R \circ R = I</math>
 
 
From <math>(2)</math>, <math>R \circ R = V \circ H = H \circ V = L \circ L</math>, so <math>R \circ R</math> can be replaced with <math>V \circ H</math>, <math>H \circ V</math>, <math>L \circ L</math> without changing the result. Suppose we choose <math>V \circ H</math>, then <cmath>(R \circ R) \circ R \circ R = (V \circ H) \circ R \circ R = V \circ (H \circ R) \circ R.</cmath>
 
From <math>(3)</math>, <math>H \circ R = L \circ H = V \circ L = R \circ V</math>, so <math>H \circ R</math> can be replaced with <math>L \circ H</math>, <math>V \circ L</math>, <math>R \circ V</math> without changing the result. Suppose we choose <math>R \circ V</math>, then <cmath>V \circ (H \circ R) \circ R = V \circ (R \circ V) \circ R = V \circ R \circ (V \circ R).</cmath>
 
From <math>(4)</math>, <math>V \circ R = L \circ V = H \circ L = R \circ H</math>, so <math>V \circ R</math> can be replaced with <math>L \circ V</math>, <math>H \circ L</math>, <math>R \circ H</math> without changing the result. Suppose we choose <math>H \circ L</math>, then <cmath>V \circ R \circ (V \circ R) =V \circ R \circ (H \circ L) = V \circ R \circ H \circ L = I.</cmath>
 
 
So, we have <math>f(4) = 4^{4-1}</math>:
 
<cmath>\underbrace{R \circ R \circ R \circ R \circ \dots R \circ R \circ R}_{2n}</cmath>
 
With <math>2n</math> <math>R</math> transformations, it will go from initial state to initial state. There are <math>2n-1</math> transformation composite operators <math>\circ</math> between the transformations, and each pair of transformations surrounding the transformations composite operator <math>\circ</math> have <math>4</math> options. So, we have <math>f(2n) = 4^{2n-1}</math>, from which <math>f(20) = 4^{20-1} = \boxed{\textbf{(C)}\ 2^{38}}</math>.
 
 
<u><b>Side Note</b></u>
 
 
<math>(2)</math>, <math>(3)</math>, <math>(4)</math> are equivalent. Here I will prove <math>(2)</math> is equivalent to <math>(3)</math>.
 
 
From <math>(1)</math>, <math>R \circ L = V \circ V</math>
 
 
<math>H \circ (R \circ L) = H \circ (V \circ V) = (H \circ V) \circ V</math>
 
 
From <math>(2)</math>, <math>H \circ V = V \circ H = L \circ L</math>
 
 
<math>(H \circ V) \circ V = (V \circ H) \circ V = V \circ (H \circ V) = V \circ (L \circ L)</math>
 
 
So, <math>(H \circ R) \circ L = H \circ (R \circ L) = V \circ (L \circ L) = (V \circ L) \circ L</math>
 
 
<math>H \circ R = V \circ L</math>, which is <math>(3)</math>
 
 
~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen]
 
  
 
==Video Solutions==
 
==Video Solutions==

Revision as of 12:54, 8 November 2022

The following problem is from both the 2020 AMC 10B #23 and 2020 AMC 12B #19, so both problems redirect to this page.

Problem

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.)

$\textbf{(A)}\ 2^{37} \qquad\textbf{(B)}\ 3\cdot 2^{36} \qquad\textbf{(C)}\ 2^{38} \qquad\textbf{(D)}\ 3\cdot 2^{37} \qquad\textbf{(E)}\ 2^{39}$

Solution 1

For each transformation:

  1. Each labeled vertex will move to an adjacent position.
  2. The labeled vertices will maintain the consecutive order $ABCD$ in either direction (clockwise or counterclockwise).
  3. $L$ and $R$ will retain the direction of the labeled vertices, but $H$ and $V$ will alter the direction of the labeled vertices.

After the $19$th transformation, vertex $A$ will be at either $(1,-1)$ or $(-1,1).$ All possible configurations of the labeled vertices are shown below: [asy] /* Made by MRENTHUSIASM */ unitsize(7mm); label("$A$",(1,0)); label("$B$",(1,1)); label("$C$",(0,1)); label("$D$",(0,0));  label("$C$",(5,0)); label("$D$",(5,1)); label("$A$",(4,1)); label("$B$",(4,0));  label("$A$",(9,0)); label("$D$",(9,1)); label("$C$",(8,1)); label("$B$",(8,0));  label("$C$",(13,0)); label("$B$",(13,1)); label("$A$",(12,1)); label("$D$",(12,0));  label("\textbf{Configuration}",(-5,0.5)); label("\textbf{The 20th}",(-5,-1.5)); label("\textbf{Transformation}",(-5,-2.25)); label("$L$",(0.5,-1.875)); label("$R$",(4.5,-1.875)); label("$H$",(8.5,-1.875)); label("$V$",(12.5,-1.875)); [/asy] Each sequence of $19$ transformations generates one valid sequence of $20$ transformations. Therefore, the answer is $4^{19}=\boxed{\textbf{(C)}\ 2^{38}}.$

~MRENTHUSIASM

Solution 2

Let $(+)$ denote counterclockwise/starting orientation and $(-)$ denote clockwise orientation. Let $1,2,3,$ and $4$ denote which quadrant $A$ is in.

Realize that from any odd quadrant and any orientation, the $4$ transformations result in some permutation of $(2+, 2-, 4+, 4-).$

The same goes that from any even quadrant and any orientation, the $4$ transformations result in some permutation of $(1+, 1-, 3+, 3-).$

We start our first $19$ moves by doing whatever we want, $4$ choices each time. Since $19$ is odd, we must end up on an even quadrant.

As said above, we know that exactly one of the four transformations will give us $(1+),$ and we must use that transformation.

Thus, the answer is $4^{19}=\boxed{\textbf{(C)}\ 2^{38}}.$

Solution 3

Notice that any pair of two of these transformations either swaps the $x$ and $y$-coordinates, negates the $x$ and $y$-coordinates, swaps and negates the $x$ and $y$-coordinates, or leaves the original unchanged. Furthermore, notice that for each of these results, if we apply another pair of transformations, one of these results will happen again, and with equal probability. Therefore, no matter what state after we apply the first $19$ pairs of transformations, there is a $\frac14$ chance the last pair of transformations will return the figure to its original position. Therefore, the answer is $\frac{4^{20}}4 = 4^{19} = \boxed{\textbf{(C)}\ 2^{38}}.$

Solution 4

The total number of sequence is $4^{20}=2^{40}.$

Note that there can only be even number of reflections since they result in the same anti-clockwise orientation of the verices $A,B,C,D.$ Therefore, the probability of having the same anti-clockwise orientation with the original arrangement after the transformation is $\frac{1}{2}.$

Next, even number of reflections mean that there must be even number of rotations since their sum is even. Even rotations result only in the original position or $180^{\circ}$ rotation of it.

Since rotation $R$ and rotation $L$ cancels each other out, the difference between the numbers of them define the final position. The probability of the transformation returning the vertices to the original position given that there are even number of rotations is equivalent to the probability that

$|n(R)-n(L)|\equiv0\pmod{4}$ when $|n(H)-n(V)|\equiv0\pmod{4}$
or
$|n(R)-n(L)|\equiv2\pmod{4}$ when $|n(H)-n(V)|\equiv2\pmod{4}$

which is again, $\frac{1}{2}.$

Therefore, $2^{40}\cdot\frac{1}{2}\cdot\frac{1}{2}=\boxed{\textbf{(C)}\ 2^{38}}.$

~joshuamh111

Solution 5

Hopefully, someone will think of a better one, but here is an indirect answer, use only if you are really desperate. $20$ moves can be made, and each move have $4$ choices, so a total of $4^{20}=2^{40}$ moves. First, after the $20$ moves, Point $A$ can only be in first quadrant $(1,1)$ or third quadrant $(-1,-1).$ Only the one in the first quadrant works, so divide by $2.$ Now, $C$ must be in the opposite quadrant as $A.$ Note that $B$ can be either in the second ($(-1, 1)$) or fourth quadrant ($(1, -1)$) , but we want it to be in the second quadrant, so divide by $2$ again. Now as $A$ and $B$ satisfy the conditions, $C$ and $D$ will also be at their original spot. $\frac{2^{40}}{2\cdot2}=2^{38}.$ The answer is $\boxed{\textbf{(C)}\ 2^{38}}.$

~Kinglogic

Solution 6 (Quick)

We can rotate and reflect the square freely until the $20$th step. There are $4^{19}$ ways to do this, (because for each one you could do $(L, R, H, V)$ which is equal to $2^{38}$. Once you reach the $20$th step, we have 1 choice of reflection/rotation. Therefore, we have $2^{38} \cdot \ 1 = \boxed{\textbf{(C)}\ 2^{38}}.$

Side Note

MRENTHUSIASM's Solution 1 has the explanation to why on the $20$th step, we have $1$ choice of reflection and rotation. You might think "What if it is diagonally opposite from our original position or on the original position on the $19$th step?" The answer is that because on the $19$th step is the $3$ (mod $4$th) step, we can never go to the $0$ (mod $4$th) step because we cannot reflect across a diagonal because we are merely rotating and reflecting. The reflection only takes place over the $x$ or $y$ axis, and therefore will never reflect across it diagonally. If we could reflect diagonally, it would distort the whole $x$ mod $4$ idea and this would not be a valid answer.

~Arcticturn

Video Solutions

Video Solution 1

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

~MathEx

Video Solution 2 by The Beauty of Math

https://youtu.be/Bl2kn9oVxQ8?t=348

~Icematrix

See Also

2020 AMC 10B (ProblemsAnswer KeyResources)
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
2020 AMC 12B (ProblemsAnswer KeyResources)
Preceded by
Problem 18
Followed by
Problem 20
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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png