OFO 2022 Problema 5

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Monazo

OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Mención-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
OFO - Jurado-OFO 2023 OFO - Jurado-OFO 2024
Mensajes: 381
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 17
Nivel: Exolímpico

OFO 2022 Problema 5

Mensaje sin leer por Monazo »

Joa dibujó en el pizarrón un tablero de $1\times 9$ y quiere completarlo con enteros positivos, no necesariamente distintos, de manera tal que cada número escrito resulte ser un divisor de todos los números escritos a su derecha. Si ya escribió el $360$ en el noveno casillero, ¿cuántas maneras distintas tiene de completar los ocho casilleros restantes?\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
\quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad & \textbf{360} \\ \hline
\end{array}
Soy una Estufa en Piloto
:shock:
Avatar de Usuario
Monazo

OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Mención-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
OFO - Jurado-OFO 2023 OFO - Jurado-OFO 2024
Mensajes: 381
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 17
Nivel: Exolímpico

Re: OFO 2022 Problema 5

Mensaje sin leer por Monazo »

Aquí publicaremos la solución oficial.
Soy una Estufa en Piloto
:shock:
sebach

Colaborador-Varias OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Bronce-OFO 2020 OFO - Medalla de Plata-OFO 2021
OFO - Medalla de Plata-OFO 2022 OFO - Medalla de Plata-OFO 2023 OFO - Medalla de Oro-OFO 2024
Mensajes: 202
Registrado: Dom 06 Mar, 2011 11:49 am
Medallas: 8
Nivel: Exolímpico

Re: OFO 2022 Problema 5

Mensaje sin leer por sebach »

EDIT: Esta solución está pensada para un tablero de $1$ x $8$, mala mía. Pero los razonamientos son válidos, y el código de abajo se cambia muy fácilmente (si tienen una noción de programación y quieren ver el código e intentar deducir qué habría que cambiar, adelante!). De hecho, eso es algo lindo de la programación: Extender este problema a un tablero de más columnas es híper fácil y podemos tener la respuesta en segundos.

Una solución:
Spoiler: mostrar
Un número es divisor de otro si y sólo si en su factorización en primos los exponentes de cada primo son menores o iguales al exponente del mismo factor primo en el otro número.
Veamos esto: Si un número $D$ es divisor de $N$, $N = D*x$ por lo que todos los primos de $D$ aparecerán en $N$. Y si $D = p_1^{\alpha_1}*p_2^{\alpha_2}*...*p_k^{\alpha_k} $ y $N = p_1^{\beta_1}*p_2^{\beta_2}*...*p_k^{\beta_k}*x$, con $\beta_i \geq \alpha_i$, luego $N/D = p_1^{\beta_1-\alpha_1}*p_2^{\beta_2-\alpha_2}*...*p_k^{\beta_k-\alpha_k}*x$ que es entero.

Además, notemos que si $A | B$ y $B | C$, entonces $A | C$. Por lo que basta con verificar que cada número divida al consecutivo de su derecha para que se cumpla que cada número divide a todos los de la derecha.

Entonces, contar las maneras distintas de completar los casilleros es contar las maneras distintas de hacer que cada número tenga todos los exponentes de sus números primos menores o iguales al de su derecha.
Como $360 = 2^3*3^2*5^1$, los factores primos de los números de la izquierda no podrán ser otros que $2, 3, 5$.

Entonces podemos pensar en completar a cada casillero con una terna de números, ordenada, que representa la cantidad de veces que aparece cada factor primo en el número.
Así, en vez de pensar en el número $90$, por ejemplo, pensamos en la terna (1, 2, 1) ya que $90 = 2^1*3^2*5^1$, y el $1$ sería la terna $(0, 0, 0)$.
De vuelta, hay una relación biyectiva entre ternas y números ya que podemos usar únicamente estos tres primos mencionados y la factorización es única y si un número no usa alguno de los primos simplemente completamos con un $0$ en esa posición de la terna (como en el caso del $1$ o del $15$ que será $(0, 1, 1)$).

Por qué nos ayuda pensar a los números así? Porque si queremos que un número divida al de la derecha, podemos pensar a cada posición de la terna independiente, por todo lo que acabamos de decir.

Entonces, con todo esto que igual no fue nada corto, redujimos el problema a pensar: Cuántas formas tengo de formar una secuencia no decreciente de $8$ enteros no negativos que no excedan el valor $m$? En nuestros casos $m$ tomará el valor $3$, $2$ y $1$ por el $360$. Al calcular esos $3$ valores, como son independientes, los multiplicamos para obtener el valor buscado.

Entonces, cómo contamos esto último para un cierto valor $m$? Veamos que la secuencia que vamos a tener será una cierta cantidad (que podría ser $0$) $a_0$ de números $0$, luego (porque es no decreciente) una cierta cantidad $a_1$ de números $1$, y así hasta terminar con una cierta cantidad $a_m$ de números $m$.
Podemos contar esto de dos formas: O bien incluir al $360$, por lo que $a_m > 0$ y tenemos $8$ elementos; o bien NO incluirlo, y entonces completar una secuencia de $7$ números, ya que por cómo formamos las secuencias luego siempre podremos agregar el valor $m$. Usaré la segunda forma.

Básicamente lo que tengo que contar es cómo separar a las $7$ celdas en $m$ grupos de cantidades no negativas.
Podemos pensar a las $7$ celdas como asteriscos y a las $m$ separaciones como barritas, y entonces simplemente necesitamos contar formas de ordenar estos $m+7$ elementos. Como intercambiar dos barritas nos da la misma secuencia (pues debe ser creciente, lo que estamos contando es cuántas veces aparece cada número en orden), y lo mismo con los asteriscos (si dos celdas aparecen entre dos barritas, ahí irá el mismo número, por lo que la secuencia será la misma por más que “intercambie las celdas”), la cantidad total de secuencias no decrecientes será $C(m+7, m)$.
Luego, la respuesta cuando $m=3$ de cuántas secuencias no decrecientes hay es $C(10, 3) = 120$, cuando $m=2$ es $C(9, 2) = 36$ y cuando $m=1$ es $C(8, 1) = 8$, por lo que finalmente la respuesta buscada es $120*36*8 = 34560$.

Por ejemplo, si tengo estas secuencias para cada valor de la tupla:
$0, 0, 1, 1, 1, 2, 2, 3$
$1, 1, 1, 2, 2, 2, 2, 2$
$0, 0, 1, 1, 1, 1, 1, 1$

Poniendo esos valores como exponentes de los tres factores primos mencionados, la secuencia será $3, 3, 30, 90, 90, 180, 180, 360$.
Dejo un algoritmo programado en el lenguaje Python por si a alguien le interesa. Creo que en general estos problemas de contar "cuántas formas hay de algo" son buenos ejemplo de tareas en las que la computadora nos puede ayudar, haciéndolo de manera rápida y "sin equivocarse". Obviamente el código tiene que estar bien para que la respuesta sea correcta, pero lo lindo también es que se pueden hacer pequeñas pruebas que si bien no demuestran que lo nuestro está bien, nos ayuda a pensar que sí.

Por ejemplo, muchas veces problemas como este los podemos encarar con la técnica recomendada en una charla TED, por lo que es cierta (?), que es
Spoiler: mostrar
pensar casos chicos (https://www.youtube.com/watch?v=mqWPS9LkFvo#t=52s)
Por ejemplo, en este caso podríamos
Spoiler: mostrar
empezar pensando que el número de la derecha es un $1$, ó un $8$, ó un $10$ y ver si encontramos algún patrón replicable en el $360$
.

Y si pensamos en eso, después podemos usar nuestro código para que la computadora nos diga esas respuestas, y a mano verificar que andan. Y bueno, ahí podemos pensar "
Spoiler: mostrar
listo claramente nuestro código está bien, mandale un $360$ y estás
", y aún así pifiarle. Pero bueno, habremos hecho al menos una comprobación necesaria. Que cuanto más exhaustiva mejor.

En fin, dejo el código, y como digo siempre, si a alguien le pica el bichito de interesarse por esto de la programación, sobre todo mezclada con matemática pero también independientemente, me puede escribir sin problema y hablamos. O si alguien ya se interesaba pero no sabe bien con quién hablar o lo que sea que crea que puedo ayudar, también me puede escribir.

Por qué confiar en una persona extraña sólo por compartir un foro y que se hace la piola subiendo un código en un spoiler que quizás sacó de internet? Es una buena pregunta, pero bueno, yo ofrezco :)
Spoiler: mostrar
Chequeo con código Python:

Código: Seleccionar todo

def getNumFromTerna(t):
 return 2**t[0]*3**t[1]*5**t[2]

def getWays(terna=(3, 2, 1), pos=8, secuencia=tuple([360]), contador=[0]):
 if pos == 1:
  contador[0] += 1
  if contador[0] % 10000 == 0: print(secuencia) # imprime la secuencia invertida
  return 1
 total = 0
 for i in range(terna[0]+1):
  for j in range(terna[1]+1):
   for k in range(terna[2]+1):
    nueva_terna = (i, j, k)
    total += getWays(nueva_terna, pos-1, tuple(list(secuencia) + [getNumFromTerna(nueva_terna)]))
 return total

>>> getWays()
(360, 180, 180, 180, 180, 45, 9, 1)
(360, 360, 60, 20, 4, 2, 2, 1)
(360, 360, 360, 180, 180, 60, 60, 10)
34560
Última edición por sebach el Lun 31 Ene, 2022 4:08 pm, editado 1 vez en total.
FabriATK

COFFEE - Mención-COFFEE Matías Saucedo OFO - Mención-OFO 2020 COFFEE - Mención-COFFEE Carolina González COFFEE - Mención-COFFEE Iván Sadofschi OFO - Medalla de Plata-OFO 2021
FOFO 11 años - Mención-FOFO 11 años OFO - Medalla de Plata-OFO 2022 FOFO Pascua 2022 - Mención-FOFO Pascua 2022 FOFO 12 años - Medalla-FOFO 12 años OFO - Medalla de Plata-OFO 2023
OFO - Jurado-OFO 2024
Mensajes: 60
Registrado: Mié 17 Abr, 2019 11:17 pm
Medallas: 11
Nivel: Exolímpico
Ubicación: Corrientes

Re: OFO 2022 Problema 5

Mensaje sin leer por FabriATK »

Me dió un resultado distinto
Spoiler: mostrar
Claramente, los $8$ números restantes son divisores de $360$ Y $360 = 2^3\times 3^2\times 5$
Como cada número tiene número tiene los mismos factores(y tal vez algunos más) que los de su izquierda, lo que nos interesa saber es: cuántas formas hay de ubicar el primer $2$, el primer $2^2$... y así siguiendo.
Para esto usaremos el método de los separadores. Ubicaremos primero los factores $2$ y después hacemos lo mismo con el resto:
Tenemos $8$ casillas que representamos con $8$ guiones: _ _ _ _ _ _ _ _ y tres factores $2$ que representamos con 3 separadores: | | |
Si, por ejemplo, tuviéramos algo así: |_ _ _ | _ _ _ _ _ | significaría que todos los números desde la primera hasta la tercera casilla(inclusive) tienen exactamente un factor 2, que desde la cuarta hasta la octava tienen $2$ factores $2$ y que el último factor $2$ aparece recién en la novena.
Entonces, tenemos que ver cúantas maneras hay de ubicar a los separadores entre los guiones. tenemos $8 + 3 = 11$ ubicaciones y las elegimos de a $3$: hay $C(8+3, 3)=165$
Hacemos lo mismo para los factores $3$ y $5$, y en total hay: $C(8+3, 3) \times C(8+2, 2) \times C(8+1, 1) = 66.825$
Rta: Hay $66.825$ maneras de completar las $8$ casillas restantes.
3  
sebach

Colaborador-Varias OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Bronce-OFO 2020 OFO - Medalla de Plata-OFO 2021
OFO - Medalla de Plata-OFO 2022 OFO - Medalla de Plata-OFO 2023 OFO - Medalla de Oro-OFO 2024
Mensajes: 202
Registrado: Dom 06 Mar, 2011 11:49 am
Medallas: 8
Nivel: Exolímpico

Re: OFO 2022 Problema 5

Mensaje sin leer por sebach »

Buuu tenés razón! Yo hice todo como si el tablero fuera de $1 x 8$, no de $1 x 9$.

Pero bueno los razonamientos y cuentas fueron similares.
1  
Juaco

OFO - Medalla de Bronce-OFO 2020 OFO - Mención-OFO 2021 OFO - Medalla de Bronce-OFO 2022
Mensajes: 230
Registrado: Jue 10 Oct, 2019 8:24 pm
Medallas: 3
Ubicación: Uruguay

Re: OFO 2022 Problema 5

Mensaje sin leer por Juaco »

el problema quedaba muy bien para este año si se ponían 21 casilleros y el número de la derecha es $p^3$ para que no aparezca taaaan forzado como muchas veces o buscarle la vuelta para que el número del final sea $(3^2)^2 \times 5^2 = 45^2 = 2025$
$\text{“The further removed from usefulness or practical application, the more important."}$
Responder