Question

Sea $S$ el conjunto de todas las ternas ordenadas de enteros $(a_1, a_2, a_3)$ con $1 \le a_1,$ $a_2,$ $a_3 \le 10.$ Cada terna ordenada de $S$ genera una sucesión según la regla $a_n = a_{n-1} \cdot |a_{n-2} - a_{n-3}|$ para $n \ge 4.$ Halla el número de tales sucesiones para las que $a_n = 0$ para algún $n.$

Let $S$ be the set of all ordered triples of integers $(a_1, a_2, a_3)$ with $1 \le a_1,$ $a_2,$ $a_3 \le 10.$ Each ordered triple in $S$ generates a sequence according to the rule $a_n = a_{n-1} \cdot |a_{n-2} - a_{n-3}|$ for $n \ge 4.$ Find the number of such sequences for which $a_n = 0$ for some $n.$

Respuesta

Respuesta: 494

Conceptos:recursión análisis por casos inclusión-exclusión

Nivel de dificultad: 2990

Pista pequeña:

Si dos términos consecutivos llegan a ser iguales, la sucesión alcanza $0$ dos pasos después; si difieren en $1,$ alcanza $0$ dentro de cuatro pasos

If two consecutive terms are ever equal, the sequence hits $0$ two steps later; if they differ by $1,$ it hits $0$ within four steps

Pista grande:

Cuenta las ternas cuyas entradas consecutivas son iguales o difieren en $1,$ corrigiendo los solapamientos, luego verifica qué ocurre cuando una diferencia de $2$ se encuentra con un $1$

Count triples whose consecutive entries are equal or differ by $1,$ correcting for overlaps, then check what happens when a difference of $2$ meets a $1$

Solución:

Si $a_{k-1} = a_k$ entonces $a_{k+2} = a_{k+1}|a_k - a_{k-1}| = 0,$ y si $|a_k - a_{k-1}| = 1$ entonces $a_{k+2} = a_{k+1},$ así que $a_{k+4} = 0.$ Por lo tanto toda terna de una de las formas $(j,j,k),$ $(j,k,k),$ $(j,j\pm1,k),$ $(j,k,k\pm1)$ produce un $0.$ Estas formas contienen $100 + 100 + 4 \cdot 90 = 560$ ternas, pero las ternas que encajan en dos formas se cuentan dos veces: las $10$ de la forma $(j,j,j),$ las $9$ en cada una de las seis familias $(j,j,j\pm1),$ $(j,j\pm1,j),$ $(j,j\pm1,j\pm1)$ (signos coincidentes), y las $8$ en cada una de $(j,j+1,j+2)$ y $(j,j-1,j-2).$ Eso deja $560 - 10 - 54 - 16 = 480$ ternas.

Algunas otras ternas también funcionan: si $(a_1, a_2, a_3) = (j, j\pm2, 1),$ entonces $a_4 = 2$ y $|a_4 - a_3| = 1,$ así que $a_8 = 0.$ Estas $16$ ternas incluyen $(3,1,1)$ y $(4,2,1),$ que ya fueron contadas, así que añaden $14$ nuevas, para $480 + 14 = 494.$

Ninguna otra terna llega a $0:$ si ambas diferencias consecutivas son al menos $2$ y $a_3 \ge 2,$ entonces $a_4 = a_3|a_2 - a_1| \ge 2a_3 \gt a_3$ y $|a_4 - a_3| \ge a_3 \ge 2,$ así que por inducción los términos crecen para siempre y ningún factor se anula jamás. Si en cambio $a_3 = 1$ con $|a_2 - a_1| \ge 3,$ entonces $a_4 \ge 3$ y $|a_4 - a_3| \ge 2,$ y el mismo crecimiento se impone. El conteo es $494.$

If $a_{k-1} = a_k$ then $a_{k+2} = a_{k+1}|a_k - a_{k-1}| = 0,$ and if $|a_k - a_{k-1}| = 1$ then $a_{k+2} = a_{k+1},$ so $a_{k+4} = 0.$ Hence every triple of one of the forms $(j,j,k),$ $(j,k,k),$ $(j,j\pm1,k),$ $(j,k,k\pm1)$ produces a $0.$ These forms contain $100 + 100 + 4 \cdot 90 = 560$ triples, but triples fitting two forms are counted twice: the $10$ of the form $(j,j,j),$ the $9$ in each of the six families $(j,j,j\pm1),$ $(j,j\pm1,j),$ $(j,j\pm1,j\pm1)$ (matching signs), and the $8$ in each of $(j,j+1,j+2)$ and $(j,j-1,j-2).$ That leaves $560 - 10 - 54 - 16 = 480$ triples.

A few other triples also work: if $(a_1, a_2, a_3) = (j, j\pm2, 1),$ then $a_4 = 2$ and $|a_4 - a_3| = 1,$ so $a_8 = 0.$ These $16$ triples include $(3,1,1)$ and $(4,2,1),$ which were already counted, so they add $14$ new ones, for $480 + 14 = 494.$

No other triple reaches $0:$ if both consecutive differences are at least $2$ and $a_3 \ge 2,$ then $a_4 = a_3|a_2 - a_1| \ge 2a_3 \gt a_3$ and $|a_4 - a_3| \ge a_3 \ge 2,$ so inductively the terms grow forever and no factor ever vanishes. If instead $a_3 = 1$ with $|a_2 - a_1| \ge 3,$ then $a_4 \ge 3$ and $|a_4 - a_3| \ge 2,$ and the same growth takes over. The count is $494.$

2015 AIME I Problema 9

Respuesta: 494

Nivel de dificultad: 2990

Pista pequeña:

Pista grande:

Solución:

El Problema 9 en otros años