¶ 2023 AIME I Problem 14
Problem:
The following analog clock has two hands that can move independently of each other.
Initially, both hands point to the number . 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 be the number of sequences of hand movements such that during the sequence, every possible positioning of the hands appears exactly once, and at the end of the movements, the hands have returned to their initial position. Find the remainder when is divided by .
.jpg)
Solution:
Answer (608):
Denote hand positions on the clock by ordered pairs whose coordinates are the hand positions modulo 12 . Then the initial state of the clock is represented by , and hand movements correspond to moving from ( ) to either ( ) or ( ) modulo 12. The number of possible 144-term sequences of clock movements is the number of ways to cycle through all 144 ordered pairs, returning to .
Lemma: For any sequence, the hand that advances in any movement is the same as the hand that advances 12 movements later.
Proof: Without loss of generality, suppose one of the moves is from to . Consider the state that follows ( ): because it cannot be ( ), which is already in use, it must be ( ). Likewise, ( ) must be followed by ( ), and by the same logic, ( ) must always be followed by for all . After 12 moves, the hand positions will have moved from to some satisfying , so is equivalent to for some . This proves that ( ) is followed by ( ), and completes the proof of the lemma.
Let and be the number of times each hand advances during the first 12 movements. It follows that after 12 movements, the state is and, for any positive integer , the state after movements is . Furthermore, it is possible for the clock to get back to only after an integer multiple of 12 movements. Now note that
- if (equivalently ), then the clock will return to ( 0,0 ) before 144 movements, resulting in an invalid sequence;
- if (equivalently ), then the clock will return to ( 0,0 ) for the first time after 144 movements. Moreover, from any position ( ), the clock cannot return to that position in fewer than 144 movements, so any such sequence must visit all 144 positions and is a valid sequence.
For a given , there are ways to construct a 144-term sequence. Thus the number of valid sequences is
The requested remainder is 608 .
The problems and solutions on this page are the property of the MAA's American Mathematics Competitions