Fabri escribe una lista con todos los números que satisfacen las siguientes cuatro propiedades:
Son pares.
Tienen $10$ dígitos.
No contienen al dígito $0$.
La diferencia entre cada par de dígitos consecutivos es $3$.
Por ejemplo, $1474741414$ está en la lista de Fabri, pero $2585852585$, $1471471414$ y $3636363630$ no.
Calcular la cantidad de números en la lista de Fabri.
Introduccion
Para resolver el problema vamos a pensar de atrás para adelante, es decir ver que pasa cuando el ultimo digito es $2, 4, 6, 8$ y cuales son los dígitos previos a estos. Vamos a definir $S(n)$ a la cantidad de combinaciones posibles para un cierto numero de diez dígitos, donde $n$ es el ultimo dígito.
Teorema 1: $S(2) = S(8) \land S(4) = S(6)$
Demostración:
Notemos lo siguiente si empezamos con 2 u 8:
k = 1:-----2----- | 1:-----8-----
k = 2:-----5----- | 2:-----5-----
k = 3:--2----8-- | 3:--2----8--
k = 4:--5----5-- | 4:--5----5--
...
k = 10: ??
Solamente se diferencian en la primera casilla, sin embargo todo el resto de la sucesión es la misma, por lo que cuando lleguen a $k = 10, S(2) = S(8), k\in \mathbb Z^+$
Para 4 y 6 pasa algo parecido:
k = 1:-----4----- | 1:-----6-----
k = 2:--1----7-- | 2:--3----9--
k = 3:--4----4-- | 3:--6----6--
...
k = 10: ??
En este caso las sucesiones no son idénticas, sin embargo coinciden en $S(n)$. Esto se debe a que el caso inicial se vuelve a repetir en el paso 3 para ambas, entonces tenemos una recursividad la cual implica que $S(4) = S(6)$
$\blacksquare$
Teorema 2: Formula para cualquier $k$ en el caso de 2 y 8
Demostración:
Notemos que la recursividad en estos casos es igual ya que la sucesión es prácticamente idéntica.
Llamemos $f$ a la función que cuenta cuantas combinaciones hay para una cantidad $k$ de dígitos. Viendo a simple vista tenemos que $f(k) = f(k - 1) \land f(k) = 2^{\frac{k-2}{2}}, k = 2m | m \in \mathbb Z^{+}$.
Esto es cierto ya que los términos pares forman una progresión geométrica de razón 2 y termino inicial 1.
Nota: La progresión geométrica se forma viendo la cantidad de términos para un $k$ en especifico, no para el valor de los dígitos del numero que estamos buscando las combinaciones.
$\blacksquare$
Teorema 3: Formula para cualquier $k$ en el caso de 4 y 6
Demostración:
Llamemos $g$ a la función que cuenta las combinaciones para este caso, volviendo a ver la progresión geométrica tenemos que $g(k) = g(k - 1) \land g(k) = 2^{\frac{k -1}{2}}, k = 2m +1 | m \in \mathbb Z_{0}^{+}$
Muy parecido al caso anterior, tenemos que lo términos impares forman una progresión geométrica de razón 2 y termino inicial 1.
$\blacksquare$
Respuesta al problema
Usando las formulas que demostramos antes, tenemos que hallar los valores de $S(2), S(4), S(6)$ y $S(8)$.
Caso 2 y 8
La formula que encontramos nos servía para encontrar valores pares de $k$, como nosotros queremos encontrar $k = 10$ entonces reemplazando en la formula nos quedaría:
$$f(10) = 2^{\frac{10-2}{2}}$$
$$f(10) = 2^4$$
$$f(10) = 16$$
Notemos que la cantidad de números que hay en el termino 10 coincide con la cantidad de combinaciones, ya que si miramos de abajo para arriba seria como considerar el numero de 10 dígitos completo. Por lo tanto $f(10) = S(4) = S(8) = 16$
Caso 4 y 6
La formula nos sirve para valores impares de $k$, sin embargo sabemos que $g(k) = g(k - 1)$ por lo que podemos calcular $g(11)$ y concluir que $g(11) = g(10)$
$$g(11) = 2^{\frac{11 - 1}{2}}$$
$$g(11) = 2^5$$
$$g(11) = 32$$
Por lo tanto $g(11) = g(10) = 32$, y como habíamos dicho antes $g(10)$ coincide con $S(4)$ y $S(6)$, por lo tanto $g(10) = S(4) = S(6) = 32$
Combinaciones totales
Finalmente, viendo cuantas combinaciones tenemos en total:
Total $= S(2) + S(4) + S(6) + S(8)$
Total $= 16 + 16 + 32 + 32$
Total $= 96$
$P(k,d)$ es la cantidad de numeros que son pares, tienen $k$ dígitos, no contienen al dígito $0$, la diferencia entre cada par de dígitos consecutivos es $3$, y su primer dígito es $d$
Para $k=1$ $P(k,d)=1$ si $d$ es impar y $P(k,d)=0$ si $d$ es par
El problema se puede dividir en $3$ casos:
Si el último dígito tiene resto $0$ en al division por $3$, los demás dígitos tambien ya que tienen diferencia $3$, entonces pueden ser $3$, $6$, o $9$, y como el número es par, el último es $6$.
Tambien sabemos que si el primer dígito es $6$, el siguiente solo puede ser $3$ o $9$.
Si el primer dígito es $9$, el siguiente solo puede ser $6$.
Si el primer dígito es $3$, el siguiente solo puede ser $6$.
Entonces para $k>2$:
$P(k,3)+P(k,6)+P(k,9)=P(k-1,6)+(P(k-1,3)+P(k-1,9))+P(k-1,6)=P(k-1,3)+2P(k-1,6)+P(k-1,9)$
$P(k-1,3)+2P(k-1,6)+P(k-1,9)=P(k-2,6)+2(P(k-2,3)+P(k-2,9))+P(k-2,6)=2P(k-2,3)+2P(k-2,6)+2P(k-2,9)$
$P(k,3)+P(k,6)+P(k,9)=2(P(k-2,3)+P(k-2,6)+P(k-2,9))$
Entonces por inducción:
$P(k,3)+P(k,6)+P(k,9)=2^a(P(k-2a,3)+P(k-2a,6)+P(k-2a,9))$
Con a=4:
$P(10,3)+P(10,6)+P(10,9)=2^4(P(10-8,3)+P(10-8,6)+P(10-8,9))=16(P(2,3)+P(2,6)+P(2,9))=16(P(1,3)+2P(1,6)+P(1,9))=16*2=32$
Para el caso de $1,4,7$ y $2,5,8$: podemos usar la misma formula ya que se puede reemplazar $3,6,9$ por $1,4,7$ o $2,5,8$ y las afirmaciones anteriores se siguen cumpliendo pero con resto $1$ y $2$ respectivamente.
Entonces como los numeros pueden empezar con cualquier número entre $1$ y $9$, las posibilidades son:
$P(10,3)+P(10,6)+P(10,9)+P(10,1)+P(10,4)+P(10,7)+P(10,2)+P(10,5)+P(10,8)=32*3=96$
Primero, para mayor comodidad, consideremos los números escritos al revés, es decir, de derecha a izquierda.
Ahora, por la condición del enunciado tenemos que:
- Los números empiezan con: $2$, $4$, $6$ u $8$.
- Los números no tienen $0$
- La diferencia entre dígitos consecutivos es de $3$
- Tienen $10$ dígitos
Con esto, podemos ver que los números posibles son aquellos que cumplen las siguientes expresiones regulares (dada la repetición de las secuencias):
- $25((?:2|8)5)\{4\}$
- $4((?:1|7)4)\{4\}(?:1|7)$
- $6((?:3|9)6)\{4\}(?:3|9)$
- $85((?:2|8)5)\{4\}$
Básicamente, esto muestra que:
- Luego de $2$ u $8$ viene $5$, y luego de $5$ viene $2$ u $8$
- Luego de $4$ viene $1$ o $7$ y luego de $1$ o $7$ viene $4$
- Luego de $6$ viene $3$ o $9$ y luego de $3$ o $9$ viene $6$
Por lo que tiene sentido la repetición de las secuencias. Luego, el resultado es contar las combinaciones posibles que cumplen cada una de estas expresiones regulares:
- $2^4$
- $2^4\times 2$
- $2^4\times 2$
- $2^4$
Por lo que el resultado es $2^4(1+2+2+1)=2^4\times 6=\boxed{96}$.
