Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2023 AIME I Problems/Problem 14"

(Created page with "==Solution (Matrix analysis, permutation)== Define a <math>12 \times 12</math> matrix <math>X</math>. Each entry <math>x_{i, j}</math> denotes the number of movements the lon...")
 
m (→‎Solution 1 (Drawing the Grid))
 
(25 intermediate revisions by 13 users not shown)
Line 1: Line 1:
−
==Solution (Matrix analysis, permutation)==
+
==Problem==
 +
The following analog clock has two hands that can move independently of each other.
 +
<asy>
 +
            unitsize(2cm);
 +
            draw(unitcircle,black+linewidth(2));
 +
 
 +
            for (int i = 0; i < 12; ++i) {
 +
                draw(0.9*dir(30*i)--dir(30*i));
 +
            }
 +
            for (int i = 0; i < 4; ++i) {
 +
                draw(0.85*dir(90*i)--dir(90*i),black+linewidth(2));
 +
            }
 +
            for (int i = 1; i < 13; ++i) {
 +
                label("\small" + (string) i, dir(90 - i * 30) * 0.75);
 +
            }
 +
            draw((0,0)--0.6*dir(90),black+linewidth(2),Arrow(TeXHead,2bp));
 +
            draw((0,0)--0.4*dir(90),black+linewidth(2),Arrow(TeXHead,2bp));
 +
</asy>
 +
Initially, both hands point to the number <math>12</math>. The clock performs a sequence of hand movements so that on each movement, one of the two hands moves clockwise to the next number on the clock face while the other hand does not move.
 +
 
 +
Let <math>N</math> be the number of sequences of <math>144</math> hand movements such that during the sequence, every possible positioning of the hands appears exactly once, and at the end of the <math>144</math> movements, the hands have returned to their initial position. Find the remainder when <math>N</math> is divided by <math>1000</math>.
 +
 
 +
==Solution 1 (Drawing the Grid)==
 +
 
 +
This problem is, in essence, the following:  A <math>12\times12</math> coordinate grid is placed on a (flat) torus; how many loops are there that pass through each point while only moving up or right?  In other words, Felix the frog starts his journey at <math>(0,0)</math> in the coordinate plane.  Every second, he jumps either to the right or up, until he reaches an <math>x</math>- or <math>y</math>-coordinate of <math>12</math>.  At this point, if he tries to jump to a coordinate outside the square from <math>(0,0)</math> to <math>(11,11)</math>, he "wraps around" and ends up at an <math>x</math>- or <math>y</math>- coordinate of <math>0</math>.  How many ways are there for Felix to jump on every grid point in this square, so that he ends at <math>(0,0)</math>?  This is consistent with the construction of the flat torus as <math>\mathbb Z^2/12\mathbb Z^2</math> (2-dimensional modular arithmetic.  <math>(\mathbb{Z}_{12})^2</math>)
 +
 
 +
Moving on, define a <math>\textit{path}</math> from point <math>A</math> to point <math>B</math> to be a sequence of "up"s and "right"s that takes Felix from <math>A</math> to <math>B</math>.  The <math>\textit{distance}</math> from <math>A</math> to <math>B</math> is the length of the shortest path from <math>A</math> to <math>B</math>.  At the crux of this problem is the following consideration:  The points <math>A_i=(i,12-i), i\in{0,...,11}</math> are pairwise equidistant, each pair having distance of <math>12</math> in both directions.
 +
 
 +
<asy>
 +
size(7cm);
 +
for (int x=0; x<12; ++x){
 +
for (int y=0; y<12; ++y){
 +
fill(circle((x,y),0.05));}}
 +
for (int i=0; i<12; ++i){
 +
fill(circle((i,11-i),0.1),red);}
 +
pen p=green+dashed;
 +
path u=(3,8)--(4,8)--(4,9)--(4,10)--(4,11)--(5,11)--(5,11.5);
 +
path v=(5,-0.5)--(5,0)--(5,1)--(6,1)--(6,2)--(6,3)--(6,4)--(7,4);
 +
draw(u,p);
 +
draw(v,p);
 +
pen p=blue+dashed;
 +
path u=(4,7)--(5,7)--(5,8)--(5,9)--(5,10)--(6,10)--(6,11)--(6,11.5);
 +
path v=(6,-0.5)--(6,0)--(7,0)--(7,1)--(7,2)--(7,3)--(8,3);
 +
draw(u,p);
 +
draw(v,p);
 +
</asy>
 +
 
 +
A valid complete path then joins two <math>A_i</math>'s, say <math>A_i</math> and <math>A_j</math>.  In fact, a link between some <math>A_i</math> and <math>A_j</math> fully determines the rest of the cycle, as the path from <math>A_{i+1}</math> must "hug" the path from <math>A_i</math>, to ensure that there are no gaps.  We therefore see that if <math>A_0</math> leads to <math>A_k</math>, then <math>A_i</math> leads to <math>A_{i+k}</math>.  Only the values of <math>k</math> relatively prime to <math>12</math> result in solutions, though, because otherwise <math>A_0</math> would only lead to <math>\{A_i:\exists n\in \mathbb Z:i\equiv kn\quad\text{mod 12}\}</math>.  The number of paths from <math>A_0</math> to <math>A_k</math> is <math>{12\choose k}</math>, and so the answer is
 +
 
 +
<cmath>{12\choose1}+{12\choose5}+{12\choose7}+{12\choose11}=1\boxed{608}.</cmath>
 +
 
 +
Notes:
 +
 
 +
- One can prove that the path from <math>A_{i+1}</math> must "hug" the path from <math>A_i</math> by using techniques similar to those in Solution 2.
 +
 
 +
- One can count the paths as follows:  To get from <math>A_0</math> to <math>A_i</math>, Felix takes <math>k</math> rights and <math>12-k</math> ups, which can be done in  <math>{12\choose k}</math> ways.
 +
 
 +
==Solution 2 (Simple Cyclic Permutation Analysis)==
 +
 
 +
This is more of a solution sketch and lacks rigorous proof for interim steps, but illustrates some key observations that lead to a simple solution.
 +
 
 +
Note that one can visualize this problem as walking on a <math>N \times N</math> grid where the edges warp. Your goal is to have a single path across all nodes on the grid leading back to <math>(0,\ 0)</math>. For convenience, any grid position are presumed to be in <math>\mod N</math>.
 +
 
 +
Note that there are exactly two ways to reach node <math>(i,\ j)</math>, namely <math>(i - 1,\ j)</math> and <math>(i,\ j - 1)</math>.
 +
 
 +
As a result, if a path includes a step from <math>(i,\ j)</math> to <math>(i + 1,\ j)</math>, there cannot be a step from <math>(i,\ j)</math> to <math>(i,\ j + 1)</math>. However, a valid solution must reach <math>(i,\ j + 1)</math>, and the only valid step is from <math>(i - 1,\ j + 1)</math>.
 +
 
 +
So a solution that includes a step from <math>(i,\ j)</math> to <math>(i + 1,\ j)</math> dictates a step from <math>(i - 1,\ j + 1)</math> to <math>(i,\ j + 1)</math> and by extension steps from <math>(i - a,\ j + a)</math> to <math>(i - a + 1,\ j + a)</math>. We observe the equivalent result for steps in the orthogonal direction.
 +
 
 +
This means that in constructing a valid solution, taking one step in fact dictates N steps, thus it's sufficient to count valid solutions with <math>N = a + b</math> moves of going right <math>a</math> times and <math>b</math> times up the grid. The number of distinct solutions can be computed by permuting 2 kinds of indistinguishable objects <math>\binom{N}{a}</math>.
 +
 
 +
Here we observe, without proof, that if <math>\gcd(a, b) \neq 1</math>, then we will return to the origin prematurely. For <math>N = 12</math>, we only want to count the number of solutions associated with <math>12 = 1 + 11 = 5 + 7 = 7 + 5 = 11 + 1</math>.
 +
 
 +
(For those attempting a rigorous proof, note that <math>\gcd(a, b) = \gcd(a + b, b) = \gcd(N, b) = \gcd(N, a)</math>).
 +
 
 +
The total number of solutions, noting symmetry, is thus
 +
 
 +
<cmath>2\cdot\left(\binom{12}{1} + \binom{12}{5}\right) = 1608</cmath>
 +
 
 +
This yields <math>\boxed{\textbf{608}}</math> as our desired answer.
 +
 
 +
~ cocoa @ https://www.corgillogical.com/
 +
 
 +
==Solution 3 (Matrix Analysis and Permutation)==
  
 
Define a <math>12 \times 12</math> matrix <math>X</math>.
 
Define a <math>12 \times 12</math> matrix <math>X</math>.
Line 66: Line 149:
  
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
 +
 +
 +
 +
==Video Solution==
 +
 +
https://youtu.be/tsoLZj8Dz2o
 +
 +
~MathProblemSolvingSkills.com
 +
 +
 +
 +
==Animated Video Solution==
 +
 +
https://youtu.be/A5BqIUPIbVg
 +
 +
~Star League (https://starleague.us)
 +
 +
==See also==
 +
{{AIME box|year=2023|num-b=13|num-a=15|n=I}}
 +
 +
[[Category:Intermediate Algebra Problems]]
 +
[[Category:Intermediate Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 21:01, 4 January 2024

Problem

The following analog clock has two hands that can move independently of each other. [asy] unitsize(2cm); draw(unitcircle,black+linewidth(2)); for (int i = 0; i < 12; ++i) { draw(0.9*dir(30*i)--dir(30*i)); } for (int i = 0; i < 4; ++i) { draw(0.85*dir(90*i)--dir(90*i),black+linewidth(2)); } for (int i = 1; i < 13; ++i) { label("\small" + (string) i, dir(90 - i * 30) * 0.75); } draw((0,0)--0.6*dir(90),black+linewidth(2),Arrow(TeXHead,2bp)); draw((0,0)--0.4*dir(90),black+linewidth(2),Arrow(TeXHead,2bp)); [/asy] Initially, both hands point to the number $12$. The clock performs a sequence of hand movements so that on each movement, one of the two hands moves clockwise to the next number on the clock face while the other hand does not move.

Let $N$ be the number of sequences of $144$ hand movements such that during the sequence, every possible positioning of the hands appears exactly once, and at the end of the $144$ movements, the hands have returned to their initial position. Find the remainder when $N$ is divided by $1000$.

Solution 1 (Drawing the Grid)

This problem is, in essence, the following: A $12\times12$ coordinate grid is placed on a (flat) torus; how many loops are there that pass through each point while only moving up or right? In other words, Felix the frog starts his journey at $(0,0)$ in the coordinate plane. Every second, he jumps either to the right or up, until he reaches an $x$- or $y$-coordinate of $12$. At this point, if he tries to jump to a coordinate outside the square from $(0,0)$ to $(11,11)$, he "wraps around" and ends up at an $x$- or $y$- coordinate of $0$. How many ways are there for Felix to jump on every grid point in this square, so that he ends at $(0,0)$? This is consistent with the construction of the flat torus as $\mathbb Z^2/12\mathbb Z^2$ (2-dimensional modular arithmetic. $(\mathbb{Z}_{12})^2$)

Moving on, define a $\textit{path}$ from point $A$ to point $B$ to be a sequence of "up"s and "right"s that takes Felix from $A$ to $B$. The $\textit{distance}$ from $A$ to $B$ is the length of the shortest path from $A$ to $B$. At the crux of this problem is the following consideration: The points $A_i=(i,12-i), i\in{0,...,11}$ are pairwise equidistant, each pair having distance of $12$ in both directions.

[asy] size(7cm); for (int x=0; x<12; ++x){ for (int y=0; y<12; ++y){ fill(circle((x,y),0.05));}} for (int i=0; i<12; ++i){ fill(circle((i,11-i),0.1),red);} pen p=green+dashed; path u=(3,8)--(4,8)--(4,9)--(4,10)--(4,11)--(5,11)--(5,11.5); path v=(5,-0.5)--(5,0)--(5,1)--(6,1)--(6,2)--(6,3)--(6,4)--(7,4); draw(u,p); draw(v,p); pen p=blue+dashed; path u=(4,7)--(5,7)--(5,8)--(5,9)--(5,10)--(6,10)--(6,11)--(6,11.5); path v=(6,-0.5)--(6,0)--(7,0)--(7,1)--(7,2)--(7,3)--(8,3); draw(u,p); draw(v,p); [/asy]

A valid complete path then joins two $A_i$'s, say $A_i$ and $A_j$. In fact, a link between some $A_i$ and $A_j$ fully determines the rest of the cycle, as the path from $A_{i+1}$ must "hug" the path from $A_i$, to ensure that there are no gaps. We therefore see that if $A_0$ leads to $A_k$, then $A_i$ leads to $A_{i+k}$. Only the values of $k$ relatively prime to $12$ result in solutions, though, because otherwise $A_0$ would only lead to $\{A_i:\exists n\in \mathbb Z:i\equiv kn\quad\text{mod 12}\}$. The number of paths from $A_0$ to $A_k$ is ${12\choose k}$, and so the answer is

\[{12\choose1}+{12\choose5}+{12\choose7}+{12\choose11}=1\boxed{608}.\]

Notes:

- One can prove that the path from $A_{i+1}$ must "hug" the path from $A_i$ by using techniques similar to those in Solution 2.

- One can count the paths as follows: To get from $A_0$ to $A_i$, Felix takes $k$ rights and $12-k$ ups, which can be done in ${12\choose k}$ ways.

Solution 2 (Simple Cyclic Permutation Analysis)

This is more of a solution sketch and lacks rigorous proof for interim steps, but illustrates some key observations that lead to a simple solution.

Note that one can visualize this problem as walking on a $N \times N$ grid where the edges warp. Your goal is to have a single path across all nodes on the grid leading back to $(0,\ 0)$. For convenience, any grid position are presumed to be in $\mod N$.

Note that there are exactly two ways to reach node $(i,\ j)$, namely $(i - 1,\ j)$ and $(i,\ j - 1)$.

As a result, if a path includes a step from $(i,\ j)$ to $(i + 1,\ j)$, there cannot be a step from $(i,\ j)$ to $(i,\ j + 1)$. However, a valid solution must reach $(i,\ j + 1)$, and the only valid step is from $(i - 1,\ j + 1)$.

So a solution that includes a step from $(i,\ j)$ to $(i + 1,\ j)$ dictates a step from $(i - 1,\ j + 1)$ to $(i,\ j + 1)$ and by extension steps from $(i - a,\ j + a)$ to $(i - a + 1,\ j + a)$. We observe the equivalent result for steps in the orthogonal direction.

This means that in constructing a valid solution, taking one step in fact dictates N steps, thus it's sufficient to count valid solutions with $N = a + b$ moves of going right $a$ times and $b$ times up the grid. The number of distinct solutions can be computed by permuting 2 kinds of indistinguishable objects $\binom{N}{a}$.

Here we observe, without proof, that if $\gcd(a, b) \neq 1$, then we will return to the origin prematurely. For $N = 12$, we only want to count the number of solutions associated with $12 = 1 + 11 = 5 + 7 = 7 + 5 = 11 + 1$.

(For those attempting a rigorous proof, note that $\gcd(a, b) = \gcd(a + b, b) = \gcd(N, b) = \gcd(N, a)$).

The total number of solutions, noting symmetry, is thus

\[2\cdot\left(\binom{12}{1} + \binom{12}{5}\right) = 1608\]

This yields $\boxed{\textbf{608}}$ as our desired answer.

~ cocoa @ https://www.corgillogical.com/

Solution 3 (Matrix Analysis and Permutation)

Define a $12 \times 12$ matrix $X$. Each entry $x_{i, j}$ denotes the number of movements the longer hand moves, given that two hands jointly make $12 \left( i - 1 \right) + \left( j - 1 \right)$ movements. Thus, the number of movements the shorter hand moves is $12 \left( i - 1 \right) + \left( j - 1 \right) - x_{i, j}$.

Denote by $r_{i, j}$ the remainder of $x_{i, j}$ divided by 12. Denote by $R$ this remainder matrix.

If two hands can return to their initial positions after 144 movements, then $r_{12, 12} = 0$ or 11. Denote by $S_0$ (resp. $S_{11}$) the collection of feasible sequences of movements, such that $r_{12, 12} = 0$ (resp. $r_{12, 12} = 11$).

Define a function $f : S_0 \rightarrow S_{11}$, such that for any $\left\{ x_{i,j} , \ \forall \ i, j \in \left\{ 1, 2, \cdots , 12 \right\} \right\} \in S_0$, the functional value of the entry indexed as $\left( i, j \right)$ is $12 \left( i - 1 \right) + \left( j - 1 \right) - x_{i, j}$. Thus, function $f$ is bijective. This implies $| S_0 | = | S_{11} |$.

In the rest of analysis, we count $| S_0 |$.

We make the following observations:

\begin{enumerate} \item $x_{1, 1} = 0$ and $12 | x_{12, 12}$.

These follow from the definition of $S_0$.

\item Each column of $R$ is a permutation of $\left\{ 0, 1, \cdots , 11 \right\}$.

The reasoning is as follows. Suppose there exist $i < i'$, $j$, such that $r_{i, j} = r_{i', j}$. Then this entails that the positions of two hands after the $\left( 12 \left( i' - 1 \right) + \left( j - 1 \right) \right)$th movement coincide with their positions after the $\left( 12 \left( i - 1 \right) + \left( j - 1 \right) \right)$th movement.

\item For any $j \in \left\{ 1, 2 ,\cdots , 11 \right\}$, $x_{i, j+1} - x_{i, j}$ is equal to either 0 for all $i$ or 1 for all $i$.

The reasoning is as follows. If this does not hold and the $j$th column in $R$ is a permutation of $\left\{ 0, 1, \cdots , 12 \right\}$, then the $j+1$th column is no longer a permutation of $\left\{ 0, 1, \cdots , 12 \right\}$. This leads to the infeasibility of the movements.

\item $x_{i+1, 1} = x_{i, 12}$ for any $i \in \left\{ 1, 2, \cdots , 11 \right\}$.

This follows from the conditions that the $12$th column in $R$ excluding $r_{12, 12}$ and the first column in $R$ excluding $x_{1, 1}$ are both permutations of $\left\{ 1, 2, \cdots , 11 \right\}$.

\end{enumerate}

All observations jointly imply that $x_{i, 12} = i \cdot x_{1, 12}$. Thus, $\left\{ r_{1, 12}, r_{2, 12} , \cdots , r_{11, 12} \right\}$ is a permutation of $\left\{ 1, 2, \cdots , 11 \right\}$. Thus, $x_{1, 12}$ is relatively prime to 12.

Because $x_{1, 1} = 0$ and $x_{1, 12} - x_{1, 1} \leq 11$, we have $x_{1, 12} = 1$, 5, 7, or 11.

Recall that when we move from $x_{1, 1}$ to $x_{1, 12}$, there are 11 steps of movements. Each movement has $x_{1, j+1} - x_{i, j} = 0$ or 1. Thus, for each given $x_{1, 12}$, the number of feasible movements from $x_{1, 1}$ to $x_{1, 12}$ is $\binom{11}{x_{1, 12}}$.

Therefore, the total number of feasible movement sequences in this problem is \begin{align*} | S_0 | + | S_{11} | & = 2 | S_0 | \\ & = 2 \cdot \sum_{x_{1, 12} = 1, 5, 7, 11} \binom{11}{x_{1, 12}} \\ & = 2 \left( 11 + 462 + 330 + 1 \right) \\ & = 1608 . \end{align*}

Therefore, the answer is $\boxed{\textbf{(608) }}$.

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

Video Solution

https://youtu.be/3DtJB78aua4

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)


Video Solution

https://youtu.be/tsoLZj8Dz2o

~MathProblemSolvingSkills.com


Animated Video Solution

https://youtu.be/A5BqIUPIbVg

~Star League (https://starleague.us)

See also

2023 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 13 		Followed by
Problem 15
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2023_AIME_I_Problems/Problem_14&oldid=209914"