OMAlbum - Problema #A019

[Matías V5]

Usando los dígitos del $1$ al $9$, una vez cada uno, Iván quiere formar un número de nueve dígitos que cumpla la siguiente condición: si dos dígitos están en posiciones consecutivas, el número que forman tiene que ser múltiplo de $7$ o de $13$ (puede ser múltiplo de ambos a la vez). ¿Qué número puede formar Iván?

[Genericool]

Primero hice una lista de los múltiplos de dos dígitos de $7$ o $13$.

$\;\;7: 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98$
$13: 13, 26, 39, 52, 65, 78, 91$

Descartamos $70$ porque el $0$ no es un dígito válido y $77$ porque no podemos repetir ningún dígito. Entonces el único número que utiliza el $7$ es $78$. Esto nos da la pauta de que no puede haber dígitos antes del $7$. El número de Iván debe comenzar con $78$.

La única posibilidad que comienza con $8$ es $84$, de modo que el número de Iván comienza con $784$.

Luego del $4$ hay dos posibilidades: $2$ o $9$. Los posibles comienzos del número de Iván son $7842$ y $7849$.

Expandiendo $7842$, puede seguir $1$ o $6$ porque el $8$ ya fue usado. Los posibles comienzos del número de Iván son $78421$, $78426$ y $7849$.

Con $78421$, debe seguir $3$ porque el $4$ ya fue usado. Luego del $3$ puede seguir $5$ o $9$. Los posibles comienzos del número de Iván son $7842135$, $7842139$, $78426$ y $7849$.

Con $7842135$, debe seguir $6$ porque el $2$ ya fue usado. Ya no podemos seguir porque tanto el $3$ como el $5$ ya están usados. Los posibles inicios son $7842139$, $78426$ y $7849$.

Con $7842139$ no podemos seguir porque tanto el $1$ como el $8$ ya están usados. Los posibles inicios son $78426$ y $7849$.

Con $78426$, puede seguir $3$ o $5$. Los posibles inicios son $784263$, $784265$ y $7849$.

Con $784263$, puede seguir $5$ o $9$. Los posibles inicios son $7842635$, $7842639$, $784265$ y $7849$.

Con $7842635$ no podemos seguir porque tanto el $2$ como el $6$ ya están usados. Los posibles inicios son $7842639$, $784265$ y $7849$.

Con $7842639$ debe seguir $1$ porque $8$ ya fue usado. Ya no podemos seguir porque tanto el $3$ como el $4$ fueron usados. Los posibles inicios son $784265$ y $7849$.

Con $784265$ no podemos seguir porque tanto el $2$ como el $6$ ya están usados. El inicio debe ser $7849$.

Después del $9$ viene el $1$ porque el $8$ ya fue usado. El inicio debe ser $78491$.

Después del $1$ viene el $3$ porque el $4$ ya fue usado. El inicio debe ser $784913$.

Después del $3$ viene el $5$ porque el $9$ ya fue usado. El inicio debe ser $7849135$.

Con $7849135$, puede seguir $2$ o $6$. Los posibles inicios son $78491352$ y $78491356$.

Con $78491356$ no podemos seguir porque $3$ y $5$ ya fueron usados. El inicio debe ser $78491352$.

Terminamos con el $6$ y el número es $784913526$.

Mi explicación es menos elegante que un sánguche de mortadela, pero la comparto porque lo que vale es el algoritmo de búsqueda.

[MRP]

Spoiler: mostrar

Lo primero que hice fue colocar todos los múltiplos de 7 y de 13 que resulten de 2 dígitos
y quedaron 13 26 39 52 65 78 91 y 14 21 28 35 42 49 56 63 70 77 84 91 98
de estos elimine el 70 por que el cero no estaba y el 77 por que se repetía el 7 y los ordene
13 14 21 26 28 35 39 42 49 52 56 63 65 78 84 91 98
de ahí veo que el 7 solo estaba en el 78
y ahí mi comienzo
78
luego solo el 84
y voy formando 784
luego podía ser 42 o 49
del 42 tenia 3 caminos a seguir; el 21, 26 o el 28
y desde el 49 solo el 91 ( pues el 98 no por tener el 8 ya usado)
opte por seguir por acá y sino lo hallaba volver atrás sobre los 3 caminos pendientes
del 91 solo sigue el 13 ( el 14 tiene el 4 ya usado)
luego el 35 (el 39 tiene el 9 usado)
luego el 52 0 el 56
pero desde el 56 el tramo final era el 63 0 65 ( que no servían por lo mismo)
y desde el 52 sigue el 21 28 y 26
el 21 y el 28 terminaban con 1 y 8 ( inválidos) y el 26 era el necesario
por lo tanto resulto
784913526
Seguramente haya una solución mas rápida pero no la encontré.