Torneo internacional de las ciudades Otoño 2021: Nivel Juvenil P4

Problemas que aparecen en el Archivo de Enunciados.
Uriel J

OFO - Mención-OFO 2019 FOFO 9 años - Mención Especial-FOFO 9 años COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Bronce-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020
COFFEE - Mención-COFFEE Carolina González COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021
OFO - Medalla de Plata-OFO 2022
Mensajes: 37
Registrado: Jue 29 Nov, 2018 2:46 pm
Medallas: 11
Nivel: 2

Torneo internacional de las ciudades Otoño 2021: Nivel Juvenil P4

Mensaje sin leer por Uriel J »

En el pizarrón está escrito el número $7$. Ana y Beto, por turnos (comienza Ana) le agregan un nuevo dígito al número del pizarrón: este nuevo dígito se puede escribir al comienzo, si no se está agregando el $0$, entre dos dígitos ya escritos o al final. Si luego del turno de alguno de los dos jugadores el número del pizarrón es un cuadrado perfecto, entonces esa persona gana. ¿Es posible para alguno de los dos jugadores garantizarse la victoria?

8 PUNTOS
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
Mensajes: 176
Registrado: Dom 06 Mar, 2011 11:49 am
Medallas: 6
Nivel: Exolímpico

Re: Torneo internacional de las ciudades Otoño 2021: Nivel Juvenil P4

Mensaje sin leer por sebach »

Spoiler: mostrar
Veamos que a quien le toca jugar siempre puede garantizarse "sobrevivir un turno más". Es decir, siempre hay una jugada que haga que la siguiente persona no puede ganar.

Puede haber varias formas de ver esto, la que se me ocurrió a mí tiene que ver con "congruencia módulo $4$". Algo interesante e importante de los cuadrados perfectos es que si son pares, son múltiplos de $4$ y si son impares, son un múltiplo de $4$ más $1$. Se puede ver mirando desde qué numero parto, pensados alrededor de su resto en la divisón por $4$:
$(4k)^2 = 16k^2 = 4*(4k^2)$
$(4k+1)^2 = 16k^2 + 8k + 1 = 4*(4k^2 + 2k) + 1$
$(4k+2)^2 = 16k^2 + 16k + 4 = 4*(4k^2 + 4k + 1)$
$(4k+3)^2 = 16k^2 + 24k + 9 = 4*(4k^2 + 6k + 2) + 1$

Otra cosa que voy a usar es que el resto en la división por $4$ se puede ver con los últimos $2$ dígitos: Si un número se escribe como $Nab$ con $a,b$ dígitos, entonces el número es $N * 100 + ab = 4*(25N) + ab$, luego si $ab = 4*m + r$, el número $Nab$ será $4*(25N + m) + r$, también de resto $r$.

Pueden pensar con estas ideas cómo resolver el problema.
Spoiler: mostrar
Entonces, algo que vamos a querer hacer en nuestro turno, para que la próxima persona no pueda garantizarse ganar, es dejar al número del pizarrón con resto $2$ ó $3$ en la división por $4$, para forzar a que la persona tenga que jugar sí o sí en la cifra de la unidad o de la decena si quiere dejar un cuadrado perfecto.

Podríamos pensar entonces qué pasa si el número escrito tiene resto $0$ ó $1$ por un lado, y por otro lado pensar en qué pasa si tiene resto $2$ ó $3$. Pero para no mirar esos casos por separado, voy a pensar en el caso general sin restricciones.

Supongamos que poniendo el dígito $0$ al final generamos un número de resto $r$. Luego, al poner un $1$ en vez de un $0$, el número tendría resto $r+1$. Al poner un $2$, tendría resto $r+2$ (ó $0$ si $r = 2$). Y así sucesivamente, variando el dígito final controlamos el resto en la división por $4$.
De los $10$ dígitos que podemos poner, al menos $4$ de ellos generarán un resto igual a $2$ ó $3$. Puede verse que poniendo en la unidad los dígitos $0, 4, 8$ el resto final es el mismo. Y lo mismo para los grupos $\{1, 5, 9\}, \{2, 6\}, \{3, 7\}$. Cada uno de esos grupos genera un resto distinto de $0, 1, 2, 3$, por eso al menos $4$ dígitos generan los restos mencionados, $2$ ó $3$.

Sean $a, b, c, d$ estos dígitos que, puestos en la unidad, generan un número de resto $2$ ó $3$ en la división por $4$.
Si poniendo alguno de estos dígitos en la unidad, la otra persona no puede ganar, lo jugamos, y sobreviviremos un turno más.
Ahora si poniendo el dígito $a$, la otra persona puede ganar, tendrá que hacerlo o bien poniendo un número en la unidad, o en la decena, por lo que venimos diciendo. Así elegimos el $a$, tal que fuerce a la otra persona a cambiar el resto en la división por $4$ si quiere un cuadrado perfecto.

Sea $N$ el número escrito en el pizarrón, y supongamos que dejando cualquiera de los números $Na, Nb, Nc, Nd$, la siguiente persona puede garantizarse ganar.
Esto significa que existen dígitos $e, f, g, h$ tales que:
O bien $Nae$ ó $Nea$ es un cuadrado perfecto. Y lo mismo para las otras posibles jugadas:
O bien $Nbf$ ó $Nfb$ es un cuadrado perfecto.
O bien $Ncg$ ó $Ngc$ es un cuadrado perfecto.
O bien $Ndh$ ó $Nhd$ es un cuadrado perfecto.

Ahora hay que tener cuidado con que los cuadrados perfectos podrían ser el mismo y arruinaría un argumento que voy a usar después.
La pregunta es, puede ser que para cualquiera de mis jugadas $a, b, c, d$, la otra persona pueda formar el mismo cuadrado perfecto?
La respuesto es no. Como $a, b, c, d$ son distintos, entonces a lo sumo uno de los cuadrados debe tener mi dígito en la unidad. Pero por la misma razón para que sean todos el mismo cuadrado perfecto, no puede haber dos con mi dígito en la decena. Como hay $4$, es imposible.

Ahora bien, supongamos que para cada una de mis jugadas la otra persona puede ganar en el siguiente turno, como venimos diciendo. Entonces, por el último argumento, debe haber dos números que sean cuadrados perfectos y que empiecen con los dígitos de $N$. Por ejemplo si $Nae$ y $Ngc$ fueran cuadrados perfecto distintos, vemos que empiezan con el número $N$ a la izquierda.
O sea que su diferencia es a lo sumo $99$ !!

Y ahora viene la otra clave: Entre cuadrados perfectos consecutivos la diferencia no puede ser cualquier cosa. De hecho la diferencia entre $x^2$ y $(x+1)^2$ es $(x+1)^2 - x^2 = x^2 + 2x + 1 - x^2 = 2x+1$.
O sea, que si el número $x$ tal que al cuadrado es igual a (siguiendo el ejemplo de antes) $Nae$, es mayor a $49$, la diferencia entre $Nae$ y el siguiente cuadrado perfecto será $2x+1$ que es al menos $2*50 + 1 = 101$, por lo que no empezará con $N$ a la izquierda. (Asumiendo que $Nae < Ngc$, si no es el mismo argumento para el otro número.)

Notemos que $50^2 = 2500$, o sea que si hay escritos ya $3$ dígitos en el pizarrón, necesariamente el número cuyo cuadrado va a aparecer en el pizarrón después de mi turno y el de mi contrincante será mayor a $50$. O sea que si hay escritos $3$ dígitos en el pizarrón, la persona a la que le toque jugar puede garantizarse sobrevivir un turno más observando sus jugadas $a, b, c, d$ como dijimos antes, entendiendo que va a existir una jugada de esas que no le permita ganar a quien sigue jugando ni en la unidad ni en la decena.

Nos falta ver una cosa: Que podemos llegar a tener $3$ dígitos sin que alguien gane.

Primero, veamos ejemplos con números de lo que dije antes con letras:

EJEMPLO 1
Supongamos que está escrito el número $156$.
Mis posibilidades para que, jugando en la unidad, quede en el pizarrón un número de resto $2$ ó $3$, son: $1562, 1563, 1566, 1567$.
Ahora, si yo dejo $1562$, mi contrincante puede escribir $15625 = 125^2$ y ganar.
Entonces no voy a jugar el $2$ en la unidad.

Ahora, sé que cualquier otra jugada que tengo va a ser segura. Esto es porque $124^2 = 15376$ y $126^2 = 15876$, y ambos cuadrados no empiezan con $156$, lo que si yo agrego cualquier cosa al final, dejando el $156$ al principio y forzando a mi contrincante a jugar en la unidad o en la decena, entonces el cuadrado que deberá formar es exactamente el $15625$, pero como yo no juego ni un $2$ ni un $5$ no podrá construir ese número.

EJEMPLO 2
Otro ejemplo: Está escrito el $25$. Si yo juego en la unidad y dejo alguno de los números $250, 251, 254, 255, 258, 259$, fuerzo lo que vengo diciendo. Ahora, el único cuadrado perfecto de $4$ dígitos que empieza en $25$ es $50^2 = 2500$, dado que $49^2 = 2401, 51^2 = 2601$.
Entonces, mientras no juegue el $0$ en la unidad, jugando por ejemplo el $1$ en la unidad, sé que voy a sobrevivir.

CONCLUSION
Entonces, si hay escritas $3$ cifras y me toca mí y no puedo ganar, nunca voy a dejarle a la otra persona una posición ganadora porque por qué lo haría si siempre puedo jugar algo que no le permita ganar. (Asumiendo como siempre que juego a ganar.)

Es medio tedioso llevar al juego a $3$ cifras, pero podemos ir más allá: Si hay dos cifras y el número es mayor a $25$, por el mismo razonamiento de antes del $50^2$, entonces el juego no va a terminar.

Como al principio hay un $7$, si Ana juega su primer turno en la unidad ya está, lo mismo si juega en la decena un dígito mayor a $1$. (Bueno, esto porque Ana no puede ganar al principio. Si Ana puede ganar al principio cuántas palabras al pedo. Pero como no hay un cuadrado perfecto de $2$ dígitos que termine o empiece en $7$, estamos bien, valió la pena.)
Entonces, veamos que si Ana juega y deja el $17$ primero, no puede garantizarse ganar. Ahora Beto puede dejar el número $179$ de resto $3$ en la división por $4$, forzando a Ana a jugar en la unidad o la decena si quiere ganar. Pero el único cuadrado perfecto que empieza en $17$ es $42^2 = 1764$, por lo que Ana no podrá ganar.

Entonces, como Ana no puede garantizarse ganar al principio, puede dejar por ejemplo el $71$ al principio, y a partir de ahí, ambas personas podrán garantizar que la otra no pueda ganar, y eso harán infinitamente.
Responder