Nacional 2003 N3 P2

Avatar de Usuario
julianferres_

OFO - Medalla de Bronce-OFO 2015 OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Plata-OFO 2017 OFO - Mención-OFO 2021
Mensajes: 388
Registrado: Sab 17 Sep, 2011 8:01 pm
Medallas: 4
Nivel: Exolímpico
Ubicación: Villa Ramallo, Buenos Aires

Nacional 2003 N3 P2

Mensaje sin leer por julianferres_ »

En el pizarrón están escritos los $2003$ números enteros desde $1$ hasta $2003$. Lucas debe borrar $90$ números. A continuación, Mauro debe elegir $37$ de los números que permanecen escritos. Si los $37$ números que elige Mauro forman una progresión aritmética, gana Mauro. Si no, gana Lucas. Decidir si Lucas puede elegir los $90$ números que borra de modo que se asegura la victoria.
Avatar de Usuario
Prillo

Colaborador-Varias OFO - Jurado-OFO 2015
Mensajes: 401
Registrado: Sab 18 Dic, 2010 8:52 pm
Medallas: 2

Re: Nacional 2003 N3 P2

Mensaje sin leer por Prillo »

Spoiler: mostrar
Lucas gana.

Si la razon de la progresion no es multiplo de [math], entonces alguno de sus terminos va a ser multiplo de [math] (porque [math] es primo entonces [math] es un sistema completo de restos modulo [math] para cualquier [math] no divisible por [math]). Entonces si Lucas borra todos los multiplos de [math] entre [math] y [math] (que son [math]), Mauro pierde si su progresion tiene razon no divisible por [math]. Entonces, la unica esperanza de Mauro es que la razon de su progresion sera multiplo de [math]. En este caso, si la razon es mas grande que [math], entonces es al menos [math], pero como [math], entonces la progresion no entraria en el rango entre [math] y [math] inclusive, absurdo. Entonces la razon tiene que ser exactamente [math]. En tal caso, la diferencia entre el primer y el ultimo termino es [math], y la diferencia entre terminos [math]. O sea que alguno de sus terminos deberia caer entre [math] y [math] inclusive. Pero entonces Lucas puede borrar los [math] numeros [math] (el [math] ya estaba borrado porque es multiplos de [math]), y entonces Mauro tampoco puede ganar en este caso. Entonces, borrando estos [math] numeros gana Lucas.
2  
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: 1124
Registrado: Sab 21 May, 2022 12:41 pm
Medallas: 4
Nivel: Exolímpico
Contactar:

Re: Nacional 2003 N3 P2

Mensaje sin leer por drynshock »

Es básicamente la misma que arriba pero un poco más visual.
Spoiler: mostrar
Miremos la siguiente tablita:

\begin{array}{|c|c|c|c|c|} \hline
1&2&3&4&\dots&37 \\ \hline
38&39&40&41&\dots&74 \\ \hline
75&76&77&78&\dots&111 \\ \hline
\vdots&\vdots&\vdots&\vdots&&\vdots \\ \hline
1962&1963&1964&1965&\dots&1998 \\ \hline
1999&2000&2003&&& \\ \hline
\end{array}

Vamos a jugar para Lucas, si quiere ganar, debe sacar un numero por fila, pues en caso contrario Mauro elige la sucesión de diferencia $1$ con termino inicial en el correspondiente de la primer columna y gana. Entonces, por el momento Lucas debe sacar $\frac{1998}{37} = 54$ números.

Podemos traducir las progresiones aritméticas a ir moviéndonos $x$ casillas a la derecha e $y$ casillas hacia abajo. Por ejemplo, en una progresión de diferencia igual a $38$ y termino inicial $2$ la progresión seria $2, 40, 78, \dots$ que seria moverse una para abajo y otra a la derecha. Esto nos puede dar la gran idea de que si siempre nos movemos al menos $1$ casilla a la derecha, entonces al cabo de $36$ movimientos, habremos pasado por todas las columnas.

Entonces, en base a esta idea podemos ver que si $a_n = a_0 +d(n-1)$ es la sucesión y $d \not\equiv 0 \pmod {37}$ entonces los números de Mauro nos quedarían $a_0, a_1+d, a_2+2d, \dots, a_{36}+36d$, el cuál tiene todos los restos $\pmod{37}$, es decir que si Lucas saca todos los números con un mismo resto, entonces puede ganar. Para seguir la misma solución que Prillo, digamos que saca todos los múltiplos de $37$.

Luego, Lucas no se puede mover mas para la derecha, de donde es necesario que se mueva para abajo, dando saltitos de $k$ casillas (con $k$ constante). Entonces, viendo la tabla, podemos ver que hay $\frac{1998}{37} = 54$ filas y la ultima que tiene $3$ números. Entonces, si Lucas sale desde la primer fila, dando saltitos de dos casillas en dos casillas, entonces la máxima cantidad de casillas que puede llegar a tocar son $\frac{54}{2} = 27$, es decir que su sucesión no llega a los $37$ números.

En términos matemáticos, si en la sucesión $d = 37k \land k \geq 2 \Rightarrow d \geq 74 \Rightarrow 1+74.36 = 2665 > 2003$ (tomamos $a_0 = 1$ por que es el mas chico posible) por lo que nos pasamos de la cantidad de números de la sucesión $\therefore d = 37$.

Entonces, si $d = 37$ lo podemos ver como que Mauro va bajando de a una casilla en el tablero. Y veamos que $\frac{54}{2} = 27$, por lo que Lucas podría quitar toda una fila entera de las que están en el medio bloqueándole el paso a Mauro y asegurándose la victoria. Luego, si Lucas saca los números que están en la fila correspondiente a $1+27.37 = 1000$, es decir $1000, 1001, \dots 1036$ entonces gana (notemos que el $1036$ ya lo habíamos sacado antes por ser múltiplo de $37$).

Finalmente, Lucas saco un total de $36+54 = 90$ números y vimos que Mauro no puede formar ninguna progresión aritmética. Concluimos que Lucas tiene la winning strategy.

@Bauti.md ig
Winning is first place, anything else is losing.
"Alexandra Trusova"
Responder