2023 AIME I Problems/Problem 14

Problem 14

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 = 0; i < 12; ++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 (Matrix analysis, 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)

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

Page

Toolbox

Search

2023 AIME I Problems/Problem 14

Contents

Problem 14

Solution (Matrix analysis, permutation)

Video Solution

See also