Iberoamericana 2023 - Problema 3

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: 1116
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 8
Nivel: Exolímpico

Iberoamericana 2023 - Problema 3

Mensaje sin leer por Matías V5 »

Ana y Beto juegan con una balanza de dos platillos. Tienen $2023$ pesas etiquetadas con sus pesos, que son los números $1,2,\ldots,2023$, sin que ninguno de ellos se repita. Cada jugador, en su turno, elige una pesa que todavía no estaba colocada en la balanza y la coloca en el platillo con menos peso en ese momento. Si la balanza está en equilibrio, la coloca en cualquier platillo. Ana comienza el juego, y siguen de esta manera alternativamente hasta colocar todas las pesas. Ana gana si al finalizar la balanza se encuentra equilibrada, en caso contrario gana Beto. Determine cuál de los dos jugadores tiene una estrategia ganadora y describa la estrategia.
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
Maestro Alga

OFO - Mención-OFO 2020
Mensajes: 12
Registrado: Mar 08 Oct, 2019 9:59 am
Medallas: 1
Nivel: Exolímpico

Re: Iberoamericana 2023 - Problema 3

Mensaje sin leer por Maestro Alga »

Con apoyo de @El gran Filipikachu;
Spoiler: mostrar
Vamos a demostrar que Beto es quien tiene estrategia ganadora.
Consideremos primero las últimas dos jugadas. La anteúltima es la número $2022$, por lo que corresponde al segundo jugador, es decir Beto.
Analicemos qué necesita Ana para poder ganar sin importar lo que haga Beto. Si los platillos pesan $a$ y $b$ respectivamente y las pesas restantes $x$ e $y$.
Si $a = b \to a + x = b + y $ ó $ a + y = b + x \Rightarrow x = y$ pero esto es absurdo ya que no hay pesas con pesos repetidos.
Supongamos ahora que $a > b:$ Si $b + x = a + y $ ó $ b + y = a + x$ Beto puede elegir la pesa cuyo peso evita que se cumpla la igualdad y de esta manera asegurarse la victoria.
Ahora, si Ana quiere ganar debe cumplirse que $ b + x + y = a $

Volvamos una jugada más atrás. Una observación importante para este caso es que la diferencia entre los dos platillos es siempre $ \leq 2023$ ya que si $b + x - a > 2023 \Rightarrow x > 2023$ y no tenemos algo tan pesado.
Llamemos platillo $1$ al que en la jugada $2022$ tiene peso $a$ y platillo $2$ al que tendrá peso $b$
Si Ana agrega una pesa $z$ en este turno, pudo haberla puesto en el platillo $1$ o $2$ (dependiendo de cuál sea más liviano).
Si esta pesa fue colocada en el platillo $2$, $ (b-z) + x + y + z = a $, pero Beto puede terminar con sus ilusiones ya que para este punto él va a haber jugado $1010$ veces y en estos turnos puede elegir las primeras $1009$ pesas más otra a su elección. En este caso nos quedaría que $ x + y + z \geq 1010 + 1011 + 1012 > 2023 $ pero como vimos antes, la diferencia entre los platillos no puede ser tan grande por lo que Ana solo pudo jugar en el platillo $1$. Es decir que $ (a - z) + z = b + x + y $ para que Ana pueda ganar
Esto, a su vez, como $ b \geq a - z $ nos dice que $ x + y \leq z $

Como esto de mirar el juego de atrás para adelante nos está resultando útil, vamos a volver un par de jugadas más atrás, $5$ antes de terminar el juego, y vamos a ponernos en la cabeza de Beto.
Si recuperamos la estrategia que usamos para demostrar que las diferencias nunca superan $2023$, podemos pensar que esto puede seguir siendo de utilidad ya que descartar los números más chicos nos deja con menos posibilidades para que se cumpla la desigualdad $ x + y \leq z$
Para este punto Beto ya jugó $1009$ turnos. Si decide colocar las primeras $1009$ pesas en estos, podemos separar las pesas restantes en $2$ grupos: Las que pueden actuar como $x, y$ y las que pueden actuar como $z$
En el primer grupo nos encontramos únicamente con los números $\{1010, 1011, 1012, 1013\}$ ya que $1010 + 1014 > 2023$ y en consecuencia en el segundo grupo tenemos los números $\{2021, 2022, 2023\}$
Es claro que si nos quedamos con un sólo número del primer grupo o nos quedamos sin números del segundo grupo ganamos.
Luego de jugar su turno, Ana puede dejar a Beto con:
$3$ elementos del primer grupo y $1$ del segundo $\to$ Beto puede quitar el elemento restante del segundo grupo y ganar.
$2$ elementos del primer grupo y $2$ del segundo $\to$ Beto puede quitar un elemento del primer grupo y ganar.
Si dentro de las $4$ pesas restantes tenemos $2$ del primer grupo, $1$ del segundo y otra pesa que no pertenece a ningún grupo, podemos sacar tanto una del grupo $1$ como la del grupo $2$. En cualquier otro caso Beto puede colocar cualquier pesa ya que no existirán $x,y,z$ que cumplan con la desigualdad.
Como vemos, Beto siempre puede evitar que la balanza se encuentre equilibrada, por lo que tiene la estrategia ganadora, la cual consiste en seguir los pasos ya explicados.
2  
Responder