2023 AIME I Problems/Problem 14

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)

Page

Toolbox

Search

2023 AIME I Problems/Problem 14

Solution (Matrix analysis, permutation)

Video Solution