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"

m
Line 70: Line 70:
 
{{AIME box|year=2023|num-b=13|num-a=15|n=I}}
 
{{AIME box|year=2023|num-b=13|num-a=15|n=I}}
  
−
[[Category:Intermediate Algebra Problems]]
+
[[Category:Intermediate Combinatorics Problems]]
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 18:22, 8 February 2023

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)

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=189141"