Question

Hay un conjunto de $1000$ interruptores, cada uno de los cuales tiene cuatro posiciones, llamadas $A,$ $B,$ $C,$ y $D.$ Cuando la posición de cualquier interruptor cambia, solo lo hace de $A$ a $B,$ de $B$ a $C,$ de $C$ a $D,$ o de $D$ a $A.$ Inicialmente cada interruptor está en la posición $A.$ Los interruptores están etiquetados con los $1000$ enteros distintos $2^x 3^y 5^z,$ donde $x,$ $y,$ y $z$ toman los valores $0, 1, \ldots, 9.$ En el paso $i$ de un proceso de $1000$ pasos, el $i$ -ésimo interruptor avanza un paso, y también lo hacen todos los demás interruptores cuyas etiquetas dividen la etiqueta del $i$ -ésimo interruptor. Después de completar el paso $1000,$ ¿cuántos interruptores estarán en la posición $A$ ?

There is a set of $1000$ switches, each of which has four positions, called $A,$ $B,$ $C,$ and $D.$ When the position of any switch changes, it is only from $A$ to $B,$ from $B$ to $C,$ from $C$ to $D,$ or from $D$ to $A.$ Initially each switch is in position $A.$ The switches are labeled with the $1000$ different integers $2^x 3^y 5^z,$ where $x,$ $y,$ and $z$ take on the values $0, 1, \ldots, 9.$ At step $i$ of a $1000$ -step process, the $i$ th switch is advanced one step, and so are all the other switches whose labels divide the label on the $i$ th switch. After step $1000$ has been completed, how many switches will be in position $A?$

Respuesta

Solución:

El interruptor etiquetado $d$ avanza exactamente una vez por cada paso $i$ cuya etiqueta sea múltiplo de $d.$ Los múltiplos de $2^x 3^y 5^z$ entre las etiquetas son los $2^{x'} 3^{y'} 5^{z'}$ con $x \le x' \le 9,$ etc., así que ese interruptor avanza $(10 - x)(10 - y)(10 - z)$ veces. Regresa a la posición $A$ exactamente cuando este número es múltiplo de $4.$

Escribamos $a = 10 - x,$ $b = 10 - y,$ $c = 10 - z,$ recorriendo cada uno desde $1$ hasta $10.$ Contamos las ternas en las que $abc$ no es divisible entre $4:$ o bien los tres son impares, o bien exactamente uno es par pero no divisible entre $4.$ Entre $1, \ldots, 10$ hay $5$ valores impares y $3$ valores ( $2, 6, 10$ ) que son el doble de un número impar. Eso da $5^3 = 125$ ternas del primer tipo y $3 \cdot 3 \cdot 5^2 = 225$ del segundo, o sea $350$ en total.

Por lo tanto $1000 - 350 = 650$ interruptores terminan en la posición $A.$

The switch labeled $d$ is advanced exactly once for each step $i$ whose label is a multiple of $d.$ The multiples of $2^x 3^y 5^z$ among the labels are the $2^{x'} 3^{y'} 5^{z'}$ with $x \le x' \le 9,$ etc., so that switch advances $(10 - x)(10 - y)(10 - z)$ times. It returns to position $A$ exactly when this count is a multiple of $4.$

Write $a = 10 - x,$ $b = 10 - y,$ $c = 10 - z,$ each ranging over $1$ through $10.$ We count the triples where $abc$ is not divisible by $4:$ either all three are odd, or exactly one is even but not divisible by $4.$ Among $1, \ldots, 10$ there are $5$ odd values and $3$ values ( $2, 6, 10$ ) that are twice an odd number. That gives $5^3 = 125$ triples of the first kind and $3 \cdot 3 \cdot 5^2 = 225$ of the second, or $350$ in all.

Therefore $1000 - 350 = 650$ switches end in position $A.$

1999 AIME Problema 7

Solución:

El Problema 7 en otros años