Iberoamericana 2022 - Problema 2

Problemas que aparecen en el Archivo de Enunciados.
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 OFO - Jurado-OFO 2021
Mensajes: 1114
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 8
Nivel: Exolímpico

Iberoamericana 2022 - Problema 2

Mensaje sin leer por Matías V5 »

Sea $S=\{13,133,1333,\ldots \}$ el conjunto de los enteros positivos de la forma $1\overbrace{3\ldots 3}^{n\text{ dígitos}}$, con $n\geq 1$. Consideremos una fila horizontal de $2022$ casillas, inicialmente vacías. Ana y Borja juegan de la siguiente manera: cada uno, en su turno, escribe un dígito de $0$ a $9$ en la casilla vacía situada más a la izquierda. Empieza a jugar Ana; luego ambos jugadores se alternan hasta que todas las casillas están llenas. Cuando el juego termina, en la fila se lee, de izquierda a derecha, un número $N$ de $2022$ dígitos. Borja gana si $N$ es divisible por alguno de los números que están en $S$; en caso contrario gana Ana. Determinar cuál de los dos jugadores tiene una estrategia ganadora y describirla.
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=KzTR72_srTU
Avatar de Usuario
ésta

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2017 OFO - Jurado-OFO 2018
Mensajes: 300
Registrado: Sab 16 Oct, 2010 4:55 pm
Medallas: 4
Nivel: Ñandú

Re: Iberoamericana 2022 - Problema 2

Mensaje sin leer por ésta »

Spoiler: mostrar
Veamos que Ana tiene estrategia ganadora.
Sean $s_1 \leq s_2 \leq \ldots \leq s_n \leq \ldots$ los números de $S$ ordenados de menor a mayor.
Numeramos las casillas del tablero de $0$ a $2021$ de derecha a izquierda de modo que Ana juega en las casillas impares.
La idea es que cuando a Ana le toque jugar en la casilla $i$, siempre puede elegir un dígito de manera que no importe como se llenen las casillas restantes, el número resultante no es divisible ni por $s_i$ ni por $s_{i+1}$. De esta manera, al jugar en todas las casillas impares, se asegura que número no es divisible por ningún $s_i$ con $i \leq 2022$ y como el número es de a lo sumo $2022$ dígitos, no será divisible por ningún $s_i$ con $i > 2022$.

Veamos como Ana siempre puede jugar en la casilla $i$ y asegurarse que el número final no es divisible por $s_i$ ni $s_{i+1}$:
Sea $P$ la cadena de dígitos que se escribió hasta ahora. Hay a lo sumo $8$ múltiplos de $s_i$ de $2022$ dígitos que empiezan con $P$. Supongamos que no, entonces hay al menos $9$ de estos múltiplos. Sean $m_1 \leq m_2 \leq \ldots \leq m_9$ estos múltiplos ordenados de menor a mayor. Tenemos que
$$ 8*s_i \leq m_9 - m_1 < (P+1)*10^{i+1} - P*10^{i+1} = 10^{i+1} $$
Absurdo, pues $s_i > \frac{10^{i+1}}{8}$.
Como hay $10$ digitos que Ana puede elegir y sólo $8$ posibles multiplos, hay al menos dos dígitos $d$ tal que no hay múltiplos de $s_1$ de $2022$ dígitos que empiecen con la cadena $Pd$. Por último, con un argumento similar, si $d_1$ y $d_2$ son dos de estos dígitos, para al menos uno de estos dos, digamos $d_1$, no existe un múltiplo de $s_{i+1}$ de $2022$ dígitos que empiece con $Pd_1$. Si hubiese uno tanto para $d_1$ como para $d_2$, tenemos dos múltiplos de $s_{i+1}$ a distancia menor a $10^{i+1}$, pero $s_{i+1} > 10^{i+1}$, absurdo.
Concluimos que Ana puede elegir este dígito $d_1$ y se asegura que el número final no es divisible ni por $s_i$ ni por $s_{i+1}$.

Repitiendo esta estrategia para todos sus turnos, Ana se asegura ganar el juego.
1  
Imagen
Avatar de Usuario
Lean

OFO - Medalla de Bronce-OFO 2023 FOFO 13 años - Mención-FOFO 13 años OFO - Medalla de Plata-OFO 2024
Mensajes: 176
Registrado: Vie 20 Ene, 2023 10:38 am
Medallas: 3
Nivel: 3
Ubicación: Quilmes

Re: Iberoamericana 2022 - Problema 2

Mensaje sin leer por Lean »

ésta escribió: Sab 01 Oct, 2022 4:07 pm
Spoiler: mostrar
Si hubiese uno tanto para $d_1$ como para $d_2$, tenemos dos múltiplos de $s_{i+1}$ a distancia menor a $10^{i+1}$, pero $s_{i+1} > 10^{i+1}$, absurdo.
Hola, no entendi una cosa. Si tengo $Pd_1...,Pd_2...$, dos multiplos de $s_{i+1}$ que arrancan con la cadena de digitos $P$ y despues $d_1$ o $d_2$, donde $"..."$ indica los restantes digitos de forma que estos numeros tengan $2022$ digitos, $|Pd_2...-Pd_1...|$ no es necesariamente menor a $10^{i+1}$. Mas aun si $P$ tiene pocas cifras.
"El mejor número es el 73".
Responder