OFO 2021 Problema 5

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Turko Arias

Colaborador-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023
Mensajes: 591
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 17
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

OFO 2021 Problema 5

Mensaje sin leer por Turko Arias »

Dos jugadores, $A$ y $B$, junto con otras $2021$ personas forman un círculo, de modo que $A$ y $B$ no queden en posiciones consecutivas. $A$ y $B$ juegan por turnos alternadamente, empieza $A$. Una jugada consiste en tocar a una de las personas que se encuentra a su lado, la cual debe salir del círculo. Gana el jugador que logre sacar del círculo a su oponente.
Determinar cuál de los dos jugadores tiene una estrategia ganadora, describir dicha estrategia y explicar por qué jugando de ese modo se asegura ganar siempre.

Aclaración: Cuando una persona sale del círculo, las que quedan lo "cierran", de modo que nunca quedan huecos entre personas.
Fundamentalista del Aire Acondicionado

Y todo el orgullo de ser bien bilardista
Avatar de Usuario
Turko Arias

Colaborador-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023
Mensajes: 591
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 17
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: OFO 2021 Problema 5

Mensaje sin leer por Turko Arias »

Aquí publicaremos la solución oficial
1  
Fundamentalista del Aire Acondicionado

Y todo el orgullo de ser bien bilardista
Avatar de Usuario
Sandy

OFO - Medalla de Bronce-OFO 2019 OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber FOFO 10 años - Copa-FOFO 10 años
OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años OFO - Medalla de Plata-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 280
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 11
Nivel: 3

Re: OFO 2021 Problema 5

Mensaje sin leer por Sandy »

Solución:
Spoiler: mostrar
$A$ tiene estrategia ganadora.
Sea la distancia entre dos personas la cantidad de personas que hay entre ellos. Entre cada par de personas hay dos distancias distintas.
Uno puede ganar si, cuando le toca jugar, alguna de las dos distancias es $0$. Al ser un juego finito (hay a lo sumo $2020$ turnos), evitar perder implica ganar.
Notemos que, si cuando a $A$ le toca jugar, hay una distancia par y otra impar con $B$, puede tocar a la persona del lado par y así dejarle a $B$ dos distancias impares. $B$ se verá entonces obligado a dejarle a $A$ una distancia par y otra impar. Así, $A$ puede asegurarse que a $B$ le queden siempre dos distancias impares, particularmente distintas de $0$, por lo que $B$ no podrá ganar y eventualmente $A$ ganará.
1  
Fallo inapelable.
PedroPeña

OFO - Medalla de Bronce-OFO 2021
Mensajes: 2
Registrado: Jue 28 Ene, 2021 10:16 pm
Medallas: 1
Nivel: Exolímpico

Re: OFO 2021 Problema 5

Mensaje sin leer por PedroPeña »

Spoiler: mostrar
Si consideramos como "ganar" a eliminar al otro jugador, consideraremos "perder" a eliminar una persona de la ronda que deje a A y B al lado, ya que si uno de los jugadores hace esto, el otro podría "ganar" en el siguiente turno.

Habiendo definido esto, el jugador que se asegura ganar siempre es A y su estrategia consta de hacer lo que quiera mientras se asegure de "ganar" (si tiene la posibilidad) y no "perder".
Es claro que ninguno de los jugadores quiere "perder", y ambos van a "ganar" si tienen la posibilidad; pero luego de (como máximo) 2019 jugadas, B estará obligado a "perder" porque entre él y A habrá una persona a cada lado de la ronda y tiene que eliminar alguna si o si.
Sabemos que esta situación le sucederá a B y no a A porque cada vez que A elimina a una persona de la ronda, el total de jugadores termina siendo par.
1  
Avatar de Usuario
joa.fernandez

FOFO 8 años - Mención Especial-FOFO 8 años 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 Plata-OFO 2020
FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Copa-FOFO 10 años OFO - Medalla de Oro-OFO 2021 OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
OFO - Jurado-OFO 2023
Mensajes: 84
Registrado: Jue 20 Sep, 2018 9:40 pm
Medallas: 11
Nivel: Exolímpico

Re: OFO 2021 Problema 5

Mensaje sin leer por joa.fernandez »

Me dicen por la cucaracha que esta solución es copada, así que la dejo
Spoiler: mostrar
Veamos que $A$ tiene estrategia ganadora.

Al comienzo del juego, la cantidad de personas entre $A$ y $B$ que hay en el círculo es $2021$ (el resto de las personas que están en el círculo y no son $A$ ni $B$), y es clave ver que la paridad de la cantidad de personas cuando le toca a alguno de los jugadores es invariante. En efecto, siendo $X$ la cantidad de personas entre $A$ y $B$, si juega $A$ elimina a una persona, es decir, en el turno de $B$ hay exactamente $X-1$ personas en la ronda. Luego de jugar $B$, habrá $X-2$ personas cuando le toque jugar a $A$; entonces, efectivamente la paridad de la cantidad de personas no cambia.

Sin pérdida de la generalidad, supongamos que la cantidad de personas que hay a la izquierda de $A$ hasta llegar a $B$ es mayor que las que están a la derecha de $A$ hasta llegar a $B$, en algún turno arbitrario de $A$. Luego, en este, $A$ toca a la persona que está a su izquierda (siempre y cuando $B$ no esté al lado de $A$, ya que puede tocarlo y ganar). Además, siempre en el turno de $A$ habrá más personas en alguna de las dos direcciones, ya que de lo contrario, la cantidad de personas a la izquierda de $A$ hasta llegar a $B$ sería igual a la cantidad de personas a la derecha de $A$ hasta llegar a $B$, pero esto es imposible ya que la cantidad de personas entre $A$ y $B$ sería par en un turno donde debe jugar $A$, y al principio del juego es impar.
Por lo tanto, $A$ siempre puede evitar perder, por lo que eventualmente (como la cantidad de personas entre $A$ y $B$ es finita) $B$ luego de jugar su turno quedará al lado de $A$, donde $A$ será el reluciente ganador del juego.
3  
Rotohomotecias como estilo de vida
Alexis Nahuel Sand

OFO - Mención-OFO 2021
Mensajes: 2
Registrado: Mié 26 Ago, 2020 9:07 pm
Medallas: 1
Nivel: 2

Re: OFO 2021 Problema 5

Mensaje sin leer por Alexis Nahuel Sand »

Este es un problema que me súper gustó a la hora de resolver, ya que me resultó bastante entretenido, traté de buscarle una vuelta no tan confusa.

Sin más que hablar aquí les dejo la resolución:
Spoiler: mostrar
Para empezar con este problema vamos a analizar lo siguiente:

Independientemente de las posiciones en las que se encuentren A y B, se puede decir que siempre se formará dos bloques, con esto me refiero a que desde el lado izquierdo de A hasta B habrá un bloque que contenga una cantidad de personas y a su vez desde el lado derecho de A hasta B será el otro bloque que tiene otra cantidad de personas, lo que sabemos es que al sumar la cantidad de personas qué hay en esos dos bloques nos dará un total de 2021 personas que junto con A y B son 2023 en total.

Esto es muy importante ya que nos permite saber lo siguiente:

Cuando en un bloque hay un número par de personas, en el otro si o si habrá un número impar de personas, ¿Por qué?

La respuesta es simple, el 2021 es un número impar, entonces veamos lo siguiente:
* Si en ambos bloques hay un número de personas par, al sumar a ambos el resultado sería par, ya que par + par = par, por ende, es imposible que los dos bloques tengan una cantidad de personas par, ya que la suma de ambos no nos daría 2021.
* Si en ambos bloques hay un número de personas impar, al sumar ambos el resultado sería par, ya que impar + impar= par, por ende, es imposible que los dos bloques tengan una cantidad de personas impar, ya que la suma de los dos no nos daría 2021.
* La única manera en la que la suma de la cantidad de personas en cada bloque nos de un número impar, sería en que en un bloque haya una cantidad par de personas y en el otro una cantidad impar, ya que par + impar = impar, de esta forma si sumamos la cantidad de personas qué hay en los dos bloques si nos daría 2021, ejemplo:

Bloque desde la izquierda de A hasta B: tiene 1 persona

Bloque desde la derecha de A hasta B:
2020 personas

Si sumamos la cantidad de personas de ambos bloques nos da 2021:
1+2020=2021

Ahora bien, con esto comprobamos qué hay dos bloques, uno con un número par de personas y otro con un número impar.

Como A empieza jugando debe pensar una estrategia ganadora que le permita ganar siempre, la cual es la siguiente:

Pensemos esto, siempre que A tenga el turno debe optar por sacar una persona del bloque que tenga una cantidad de personas par, ya que de esa forma cuando le toque jugar a B, le quede los dos bloques con una cantidad de personas impar, donde esa sería esa sería su estrategia ganadora, ya qué que de esta manera cuando le toque jugar a B el quede sin posibilidades, ¿Por qué?

Si A en su primer turno le deja ambos bloques a B con una cantidad de personas impar, esto imposibilita que B pueda ganar, ya que en ambos bloques hay una cantidad impar de personas y si el saca a una persona de cualquiera de esos dos bloques, le dejará a A un bloque con una cantidad par y otro con una cantidad impar de personas, donde A para asegurarse la victoria tendrá que volver a sacar a una persona de del bloque con cantidad de personas par, de modo que de nuevo en cada uno de los dos bloques haya una cantidad impar de personas al momento de que a B le toque jugar otra vez, esto le asegura ganar a A, ya que en un determinado momento en un bloque habrá una sola persona (lo cual es una cantidad impar) y en el otro otra cantidad impar de personas, como lo puede ser:

Bloque desde la izquierda de A hasta B: tiene 1 persona

Bloque desde la derecha de A hasta B:
3 personas

Siguiendo la estrategia de A, en este caso jugaría B, ya que en ambos bloques hay una cantidad impar de personas, en este ejemplo B tiene que sacar una persona del bloque desde la derecha de A, ya que si saca del otro bloque, entre B y A no quedarán personas y como luego es el turno de A, A sacaría a B del círculo, por ende, lo que puede hacer B es sacar a una persona de las tres qué hay en el bloque de la derecha de A, lo que dejaría:

Bloque desde la izquierda de A hasta B: tiene 1 persona

Bloque desde la derecha de A hasta B:
2 personas

Aquí A siguiendo su estrategia saca a una persona del bloque donde hay 2, ya que de esta forma en ambos bloques solo queda una persona (dos bloques con cantidad impar), de esta forma se asegura la victoria ya que B está obligado a sacar a una persona de unos de esos bloques, y en ese caso B quedaría al lado de A y por ende, A lo sacaría.

En fin, A tiene la estrategia ganadora, lo cual dejé demostrado en todo lo anterior.
1  
HelcsnewsXD

FOFO 9 años - Mención Especial-FOFO 9 años COFFEE - Mención-COFFEE Carolina González COFFEE - Mención-COFFEE Ariel Zylber FOFO 10 años - Mención-FOFO 10 años
Mensajes: 59
Registrado: Jue 13 Sep, 2018 8:59 am
Medallas: 4

Re: OFO 2021 Problema 5

Mensaje sin leer por HelcsnewsXD »

Un problema interesante y totalmente generalizable a cualquier número:
Resolución de este problema
Spoiler: mostrar
Digamos que $A$ y $B$ están en posiciones tales que de un lado tienen $k$ personas entre medio (con $k \neq 0 \wedge k\neq 2021$ por condición de enunciado) y del otro $2021-k$ personas. Por ello, como $2021 \equiv 1 (mod 2)$, sin pérdida de generalidad, si $k \equiv 0 (mod 2) \Leftrightarrow 2021-k \equiv 1 (mod 2)$.
Por ello, veamos que si $A$ saca una persona de $k$, quedan los dos números impares, por lo que $B$ va a tener que convertir a alguno en par, volviendo a una disposición semejante a la anterior. Es por esto que siempre se obtiene una situación similar de juego para $A$, por lo que va a tener que hacer siempre este procedimiento de dejar dos impares ya que el juego termina cuando el lado de $k$ me queda $0$ o cuando el lado de $2021-k$ queda 0 y $0\equiv 0 (mod 2)$.
Es por esto que, como $A$ puede dejar los dos lados con una cantidad impar y obliga a $B$ a poner uno con una cantidad par, se demuestra que $A$ tienen una estrategia para ganar siempre.
Generalización
Spoiler: mostrar
Es fácil ver, siguiendo esta solución, que si $A$ y $B$ juegan con una cantidad impar de otros jugadores, gana $A$.
Sin embargo, si es una cantidad par, $A$ queda en la posición de desventaja ya que, digamos que las cantidades son $k1$ y $k2$ a cada uno de los lados. Como $k1 \equiv k2 (mod 2)$ tenemos dos casos:
1) Si $k1 \equiv 0 (mod 2)$
Cuando $A$ juegue, va a quedar, sin pérdida de generalidad, que $k1 \equiv 1 \wedge k2\equiv 0$, por lo que $B$ se encuentra en la posición ganadora y debe jugar dejándole dos números impares a su contrincante.

2) Si $k2 \equiv 1 (mod 2)$
Semejante a lo anterior ya que cuando $A$ juegue, nos va a quedar, sin pérdida de generalidad, que $k1 \equiv 0 (mod 2) \wedge k2\equiv 1 (mod 2)$ y es fácil ver que tiene la misma estrategia ganadora.

Por ello, siendo $k$ la cantidad de contrincantes que tienen, si $k\equiv 1 (mod 2)$, gana $A$. Caso contrario, gana $B$
Na, clave la solución :lol:
Responder