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 |
||
Line 66: | Line 66: | ||
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com) | ~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com) | ||
+ | |||
+ | ==See also== | ||
+ | {{AIME box|year=2023|num-b=13|num-a=15|n=I}} | ||
+ | |||
+ | [[Category:Intermediate Algebra Problems]] | ||
+ | {{MAA Notice}} |
Revision as of 16:24, 8 February 2023
Solution (Matrix analysis, permutation)
Define a matrix
.
Each entry
denotes the number of movements the longer hand moves, given that two hands jointly make
movements.
Thus, the number of movements the shorter hand moves is
.
Denote by the remainder of
divided by 12.
Denote by
this remainder matrix.
If two hands can return to their initial positions after 144 movements, then or 11.
Denote by
(resp.
) the collection of feasible sequences of movements, such that
(resp.
).
Define a function , such that for any
, the functional value of the entry indexed as
is
.
Thus, function
is bijective. This implies
.
In the rest of analysis, we count .
We make the following observations:
\begin{enumerate}
\item and
.
These follow from the definition of .
\item Each column of is a permutation of
.
The reasoning is as follows. Suppose there exist ,
, such that
. Then this entails that the positions of two hands after the
th movement coincide with their positions after the
th movement.
\item For any ,
is equal to either 0 for all
or 1 for all
.
The reasoning is as follows. If this does not hold and the th column in
is a permutation of
, then the
th column is no longer a permutation of
. This leads to the infeasibility of the movements.
\item for any
.
This follows from the conditions that the th column in
excluding
and the first column in
excluding
are both permutations of
.
\end{enumerate}
All observations jointly imply that .
Thus,
is a permutation of
.
Thus,
is relatively prime to 12.
Because and
, we have
, 5, 7, or 11.
Recall that when we move from to
, there are 11 steps of movements. Each movement has
or 1.
Thus, for each given
, the number of feasible movements from
to
is
.
Therefore, the total number of feasible movement sequences in this problem is
Therefore, the answer is .
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
Video Solution
~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.