Nacional 2003 N3 P2

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

[Prillo]

Spoiler: mostrar

Lucas gana.

Si la razon de la progresion no es multiplo de [math]37, entonces alguno de sus terminos va a ser multiplo de [math]37 (porque [math]37 es primo entonces [math]\{0,r,2r,3r,\dots,36r\} es un sistema completo de restos modulo [math]37 para cualquier [math]r no divisible por [math]37). Entonces si Lucas borra todos los multiplos de [math]37 entre [math]1 y [math]2003 (que son [math]\lfloor \frac{2003}{37} \rfloor = 54), Mauro pierde si su progresion tiene razon no divisible por [math]37. Entonces, la unica esperanza de Mauro es que la razon de su progresion sera multiplo de [math]37. En este caso, si la razon es mas grande que [math]37, entonces es al menos [math]37\cdot 2 = 74, pero como [math]1 + 74 \cdot 36 = 2665 > 2003, entonces la progresion no entraria en el rango entre [math]1 y [math]2003 inclusive, absurdo. Entonces la razon tiene que ser exactamente [math]37. En tal caso, la diferencia entre el primer y el ultimo termino es [math]37 \cdot 36 = 1332, y la diferencia entre terminos [math]37. O sea que alguno de sus terminos deberia caer entre [math]1000 y [math]1036 inclusive. Pero entonces Lucas puede borrar los [math]36 numeros [math]1000,1001,1002,\dots,1035 (el [math]1036 ya estaba borrado porque es multiplos de [math]37), y entonces Mauro tampoco puede ganar en este caso. Entonces, borrando estos [math]54 + 36 = 90 numeros gana Lucas.

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