OMAlbum - Problema #A019

Reglas del Foro
Para poder publicar un mensaje en este foro necesitás tener una cuenta de OMA Foros (no es la misma que la de OMAlbum).
Podés contar cómo pensaste el problema, ideas que hayas tenido aunque no lo hayas podido terminar, preguntar dónde está el error en tu razonamiento, etcétera.
Podés comentar/ampliar sobre las ideas que hayan compartido otras personas.
Por favor, no publiques sólo la respuesta obtenida sin contar cómo lo pensaste.
Avatar de Usuario
Matías V5

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
OFO - Jurado-OFO 2018 OFO - Jurado-OFO 2020
Mensajes: 991
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 7
Nivel: Exolímpico

OMAlbum - Problema #A019

Mensaje sin leer por Matías V5 » Lun 05 Oct, 2020 7:33 pm

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?
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore!

Numberblocks - https://www.youtube.com/watch?v=SoRiOoqao5Y

Genericool
Mensajes: 7
Registrado: Mié 05 Ago, 2020 9:28 am
Nivel: Exolímpico

Re: OMAlbum - Problema #A019

Mensaje sin leer por Genericool » Lun 05 Oct, 2020 9:38 pm

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

MRP
Mensajes: 11
Registrado: Sab 13 Oct, 2018 10:01 am
Nivel: 1

Re: OMAlbum - Problema #A019

Mensaje sin leer por MRP » Lun 05 Oct, 2020 9:41 pm

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

Responder