Selectivo Ibero 2022 - P6

[NPCPepe]

Ana y Beto juegan por turnos a un juego con sus $99$ invitados (ellos no cuentan como invitados). Tienen $99$ sillas puestas en círculo; inicialmente todos los invitados están de pie. Cada jugador, en su turno, le ordena a un invitado que esté de pie que se siente en una silla vacía determinada $C$. Al mismo tiempo, si exactamente una de las sillas adyacentes a $C$ está ocupada, el invitado que la ocupa se pone de pie, y si están las dos ocupadas, el jugador decide cuál de los dos se pone de pie. Ana comienza el juego, y su objetivo es que, al cabo de algunas movidas, haya por lo menos $k$ sillas ocupadas. Determinar el mayor valor de $k$ para el que Ana puede lograr su objetivo, no importa cómo juegue Beto.

[alerodri1976]

Spoiler: mostrar

$k=34$

Spoiler: mostrar

Si $Ana$ quiere lograr el mayor número de sillas ocupadas entonces al final del juego no puede haber una secuencia de $3$ o más sillas vacías ya que en ese caso $Ana$ puede sentar a una persona en el interior de dicha secuencia y aumentar el número de sillas ocupadas. Por lo tanto, al final del juego solo puede haber $0, 1$ o $2$ sillas vacías entre dos sillas ocupadas. Llamemos $X$ a la cantidad de veces que hay $0$ sillas vacías entre dos sillas ocupadas, $Y$ a la cantidad de veces que hay $1$ silla vacía entre dos sillas ocupadas y $Z$ a la cantidad de veces que hay $2$ sillas vacías entre dos sillas ocupadas. Si al final del juego no hay secuencias de 3 o más sillas vacías entonces.

$X + 2Y + 3Z = 99$

Y el número de sillas ocupadas es

$k = X + Y + Z$.

Por lo tanto, ya sabemos que $Ana$ puede lograr un $k$ mayor o igual a $33$.

Si $k = 33$ entonces $X = 0$, $Y = 0$ y $Z = 33$ (ya que los tres tienen que ser enteros no negativos). Esto implica que hay $33$ sillas ocupadas separadas por $33$ espacios de $2$ sillas vacías. Sin perdida de generalidad podemos enumerar las sillas de $1$ a $99$ en sentido horario y suponer que las sillas que son múltiplo de $3$ están ocupadas y las otras vacías. ¿Cómo llegamos a esta secuencia de sillas?

Primero notemos que todas las sillas que son múltiplos de $3$ están pegadas a dos sillas que no son múltiplos de $3$. También sabemos que todas las sillas que no son múltiplo de $3$ tiene una silla vecina que es múltiplo de $3$ y otra que no es múltiplo de $3$.
Supongamos todas las sillas que no son múltiplo de $3$ están vacías y que le toca jugar a $Ana$.

Si $Ana$ sienta una persona en una silla que no es múltiplo de $3$ entonces sabemos que la silla que sí es múltiplo de $3$ y que está junto a la última silla que eligió $Ana$ va a estar vacía ya sea porque estaba vacía antes de que juegue $Ana$ o porque estaba ocupada y la persona tuvo que levantarse. Luego cuando le toca el turno a $Beto$ puede sentar una persona en la silla vacía múltiplo de $3$ que esta junto a la última silla de $Ana$ y levantar a esa persona.

Si $Ana$ sienta una persona en una silla que es múltiplo de $3$ entonces $Beto$ no la mueve y sienta otra persona en otra silla vacía que es múltiplo de $3$.

Entonces vemos que $Beto$ puede lograr que haya $33$ personas sentadas separadas por dos sillas vacías. Por ejemplo $Ana$ elige la silla $3$, luego Beto la $6$ y así hasta que por último $Ana$ elige la silla $99$. Sin embargo, ahora le toca jugar a $Beto$ y este sí o sí tiene sentar a una persona en una silla que no es múltiplo de $3$. Sin pérdida generalidad supongamos que $Beto$ elige la silla $2$ que está junto a la $1$ (vacía) y la $3$ (ocupada). La persona que está en la silla $3$ se levanta y ahora le toca jugar a $Ana$ quien elige sentar a un invitado en la silla $4$. Como las sillas $3$ y $5$ están vacías entonces no se levanta nadie y el número de sillas ocupadas aumenta a $k = 34$. Luego le toca jugar a $Beto$ nuevamente y supongamos que elige la silla $3$ y hace que desocupe la silla $4$. Por último podemos ver que sin importar que silla elija $Ana$ el número de personas sentadas no aumenta y Beto puede deshacer la jugada de $Ana$ lo cual, podemos decir, que le pone un fin al juego.