OFO 2024 Problema 1

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

OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber OFO - Medalla de Plata-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años
OFO - Medalla de Plata-OFO 2022 FOFO Pascua 2022 - Medalla-FOFO Pascua 2022 FOFO 12 años - Medalla-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 59
Registrado: Lun 08 Oct, 2018 2:31 pm
Medallas: 11
Nivel: Exolímpico

OFO 2024 Problema 1

Mensaje sin leer por NicoRicci »

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.
OWEEEEEEE
Avatar de Usuario
NicoRicci

OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber OFO - Medalla de Plata-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años
OFO - Medalla de Plata-OFO 2022 FOFO Pascua 2022 - Medalla-FOFO Pascua 2022 FOFO 12 años - Medalla-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 59
Registrado: Lun 08 Oct, 2018 2:31 pm
Medallas: 11
Nivel: Exolímpico

Re: OFO 2024 Problema 1

Mensaje sin leer por NicoRicci »

Aquí publicaremos la solución oficial.
OWEEEEEEE
Avatar de Usuario
drynshock

FOFO 13 años - Mención-FOFO 13 años OFO - Medalla de Bronce-OFO 2024 FOFO Pascua 2024 - Copa-FOFO Pascua 2024 FOFO 14 años - Mención-FOFO 14 años
Mensajes: 1132
Registrado: Sab 21 May, 2022 12:41 pm
Medallas: 4
Nivel: Exolímpico
Contactar:

Re: OFO 2024 Problema 1

Mensaje sin leer por drynshock »

Problema 1 OFO 2024
Spoiler: mostrar
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$

Respuesta: La lista de Fabi tiene 96 números.
1  
@Bauti.md ig
Winning is first place, anything else is losing.
"Alexandra Trusova"
EmRuzak

OFO - Medalla de Plata-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años OFO - Medalla de Plata-OFO 2022 OFO - Medalla de Oro-OFO 2024
Mensajes: 68
Registrado: Dom 13 Dic, 2020 2:17 am
Medallas: 4
Nivel: Exolímpico

Re: OFO 2024 Problema 1

Mensaje sin leer por EmRuzak »

Spoiler: mostrar
$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.

$P(10,1)+P(10,4)+P(10,7)=2^4(P(10-8,1)+P(10-8,4)+P(10-8,7))=16(P(2,1)+P(2,4)+P(2,7))=16(P(1,1)+2P(1,4)+P(1,7))=16*2=32$

$P(10,2)+P(10,5)+P(10,8)=2^4(P(10-8,2)+P(10-8,5)+P(10-8,8))=16(P(2,2)+P(2,5)+P(2,8))=16(P(1,2)+2P(1,5)+P(1,8))=16*(1+1)=32$

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$
Avatar de Usuario
HelcsnewsXD

FOFO 9 años - Mención Especial-FOFO 9 años COFFEE - Mención-COFFEE Carolina González COFFEE - Mención-COFFEE Ariel Zylber FOFO 10 años - Mención-FOFO 10 años
Mensajes: 64
Registrado: Jue 13 Sep, 2018 8:59 am
Medallas: 4
Nivel: Exolímpico
Ubicación: Córdoba, Argentina
Contactar:

Re: OFO 2024 Problema 1

Mensaje sin leer por HelcsnewsXD »

Que no se note que estudio computación (?
Spoiler: mostrar
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}$.
Na, clave la solución :lol:
Responder