Question

El siguiente reloj analógico tiene dos manecillas que pueden moverse independientemente una de la otra.

Inicialmente, ambas manecillas apuntan al número $12.$ El reloj realiza una secuencia de movimientos de manecillas de modo que en cada movimiento, una de las dos manecillas se mueve en el sentido de las agujas del reloj hasta el siguiente número de la esfera mientras que la otra manecilla no se mueve.

Sea $N$ el número de secuencias de $144$ movimientos de manecillas tales que, durante la secuencia, cada posible posición de las manecillas aparece exactamente una vez, y al final de los $144$ movimientos, las manecillas han regresado a su posición inicial. Halla el resto cuando $N$ se divide entre $1000.$

The following analog clock has two hands that can move independently of each other.

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.$

Respuesta

Solución:

Registra las manecillas como un par ordenado $(a, b) \in \mathbb{Z}_{12} \times \mathbb{Z}_{12};$ cada movimiento reemplaza $(a, b)$ por $(a+1, b)$ o $(a, b+1),$ así que una secuencia válida es un recorrido cerrado por las $144$ posiciones; de forma equivalente, una elección, en cada posición, de qué manecilla se mueve a continuación. Ordena las posiciones en $12$ filas según $b,$ y sea $S_b \subseteq \mathbb{Z}_{12}$ el conjunto de valores de $a$ en los que el recorrido abandona la fila $b$ (un $b$ -movimiento). Un $b$ -movimiento desde la fila $b - 1$ entra en la fila $b$ con el mismo valor de $a$ y el recorrido luego avanza por valores consecutivos de $a$ hasta su siguiente salida. Para que estos tramos cubran la fila $b$ exactamente una vez deben particionar $\mathbb{Z}_{12},$ lo que obliga a que cada punto de entrada esté un paso después de una salida: $S_{b-1} = S_b + 1.$ En particular, cada $S_b$ tiene el mismo tamaño $c,$ y $S_b = S_0 - b.$

Salir de la fila $b$ en su $i$ -ésima salida (en orden cíclico) conduce a un tramo que termina en la $(i+1)$ -ésima salida de la fila $b + 1:$ cada $b$ -movimiento aumenta el índice de fila en $1$ módulo $12$ y el índice de salida en $1$ módulo $c.$ Por lo tanto el recorrido se cierra tras $\operatorname{lcm}(12, c)$ $b$ -movimientos, mientras que un recorrido completo debe usar las $12c$ salidas, así que el recorrido es un solo ciclo por las $144$ posiciones precisamente cuando $\gcd(c, 12) = 1.$ Recíprocamente, cada elección de $S_0$ con $\gcd(|S_0|, 12) = 1$ produce exactamente una secuencia de movimientos válida desde la posición inicial.

Por lo tanto $\begin{aligned} N &= \binom{12}{1} + \binom{12}{5} \\ &\quad {}+ \binom{12}{7} + \binom{12}{11} \\ &= 12 + 792 + 792 \\ &\quad {}+ 12 = 1608, \end{aligned}$ y el resto cuando $N$ se divide entre $1000$ es $608.$

Record the hands as an ordered pair $(a, b) \in \mathbb{Z}_{12} \times \mathbb{Z}_{12};$ each movement replaces $(a, b)$ by $(a+1, b)$ or $(a, b+1),$ so a valid sequence is a closed tour through all $144$ positions — equivalently, a choice, at each position, of which hand moves next. Sort the positions into $12$ rows according to $b,$ and let $S_b \subseteq \mathbb{Z}_{12}$ be the set of $a$ -values at which the tour leaves row $b$ (a $b$ -move). A $b$ -move from row $b - 1$ enters row $b$ at the same $a$ -value, and the tour then runs through consecutive $a$ -values until its next exit. For these runs to cover row $b$ exactly once they must partition $\mathbb{Z}_{12},$ which forces each entry point to sit one step past an exit: $S_{b-1} = S_b + 1.$ In particular every $S_b$ has the same size $c,$ and $S_b = S_0 - b.$

Leaving row $b$ at its $i$ -th exit (in cyclic order) leads to a run ending at the $(i+1)$ -st exit of row $b + 1:$ each $b$ -move advances the row index by $1$ modulo $12$ and the exit index by $1$ modulo $c.$ The tour therefore closes after $\operatorname{lcm}(12, c)$ $b$ -moves, while a full tour must use all $12c$ exits, so the tour is a single cycle through all $144$ positions precisely when $\gcd(c, 12) = 1.$ Conversely, every choice of $S_0$ with $\gcd(|S_0|, 12) = 1$ yields exactly one valid movement sequence from the starting position.

Hence $\begin{aligned} N &= \binom{12}{1} + \binom{12}{5} \\ &\quad {}+ \binom{12}{7} + \binom{12}{11} \\ &= 12 + 792 + 792 \\ &\quad {}+ 12 = 1608, \end{aligned}$ and the remainder when $N$ is divided by $1000$ is $608.$

2023 AIME I Problema 14

Solución:

El Problema 14 en otros años