Sea $n\geq 3$ un entero. En una hoja de papel se marcan el centro y los $n$ vértices de un polígono de $n$ lados. Ana y Beto juegan del siguiente modo: cada uno en su turno elige un vértice y traza el segmento que lo une con uno de sus vértices vecinos o con el centro del polígono, con la condición que ese segmento no se haya trazado en jugadas anteriores. Gana el que logra que luego de su jugada sea posible viajar de cualquier punto marcado a cualquier otro punto marcado recorriendo exclusivamente segmentos trazados a lo largo del juego. Ana juega en primer lugar.
Para cada entero $n\geq 3$, determinar cuál de los dos jugadores tiene estrategia ganadora y dar dicha estrategia.
Nota. Dos vértices son vecinos si el segmento que los une es un lado del polígono.
Vamos a demostrar que $n$ impar gana Ana e $n$ par gana Beto. Usaremos inducción:
Los casos $n=3$ y $n=4$ funcionan [se deja como ejercicio al lector probarlo].
Ahora, vamos a demostrar que si se cumple para $n$, se cumple para $n+2$. Tomemos tres vertices consecutivos $A_1A_2A_3$ del polígono $A_1A_2A_3\dots A_{n+2}$. Ahora, construimos otro polígono $B_1B_2B_2\cdots B_n$ donde $B_1$ representa el grupo $A_1A_2A_3$ y $B_i$ representa $A_{i+2}$ para $i>1$. Ahora, Ana o Beto van a aplicar la estrategia para el $n$-ágono $B_1B_2B_2\cdots B_n$ en $A_1A_2A_3\dots A_{n+2}$ de la siguiente forma:
Conectar $A_{n+2}A_1$ representa $B_nB_1$ y conectar $A_3A_4$ representa conectar $B_1B_2$.
Conectar el primer $A_iO$ con $1\leq i\leq 3$ representa conectar $B_1O$
Si el jugador que no tiene la estrategia coloca $A_1A_2$ ó $A_2A_3$, el ganador coloca el otro (el jugador que gana no puede colocar el primero de estos segmentos, ya que no pertenecen al polígono $B_1B_2B_2\cdots B_n$ sobre el cual hace la estrategia).
Si el jugador perdedor coloca el segundo $A_iO$ con $1\leq i\leq 3$, el ganador coloca el tercero.
Con todo esto, notamos que la propiedad se cumple en $A_1A_2A_3\dots A_{n+2}$ si y sólo si lo hace en $B_1B_2B_2\cdots B_n$. Entonces, el que tenía estrategia ganadora en $n$, la tiene en $n+2$, y estamos.
Que pasa si Ana aplica su estrategia de $n=3$ para $n=5$ y se juega asi:
- Ana = $(A_4, A_5) = (B_2, B_3)$
- Beto = $(A_2, O) = (B_1, O)$
- Ana = $(A_4, O) = (B_2, O)$ [Aca ya gana Ana para $n = 3$, pero el juego sigue para $n=5$]
- Beto = $(A_5, O)$.
- No importa que haga Ana gana Beto en la siguiente jugada.
Que pasa si Ana aplica su estrategia de $n=3$ para $n=5$ y se juega asi:
- Ana = $(A_4, A_5) = (B_2, B_3)$
- Beto = $(A_2, O) = (B_1, O)$
- Ana = $(A_4, O) = (B_2, O)$ [Aca ya gana Ana para $n = 3$, pero el juego sigue para $n=5$]
- Beto = $(A_5, O)$.
- No importa que haga Ana gana Beto en la siguiente jugada.
BrunZo escribió: ↑Jue 11 Abr, 2019 8:35 pm
la propiedad se cumple en $A$ si y sólo si lo hace en $B$.
lo cual es falso. En particular, el problema está en que, al tomar que $B_1=A_1A_2A_3$, se está asumiendo que $A_1A_2A_3$ están conectados.
Igualmente, esto se puede arreglar (creo), haciendo que el ganador conecte $A_1A_2A_3$ verdaderamente.
Explicado así nomás, para el caso par habría que analizar, dependiendo de si Ana usa el centro o no, que pasa al $A_1A_2A_3$ ó $A_1OA_3$ están conectados. Para el caso impar, Ana debería usar sus primeros dos turnos para obtener alguno de los casos de arriba, y se debería reforzar la hipótesis inductiva a "no importa como Ana coloque el primero", para no tener problemas con el primer movimiento de Beto. Creo que así estaríamos...
Yo digo que si $n$ es par gana Beto y si $n$ es impar gana Ana.
Es claro que en cada momento hay una única manera de dividir a los puntos de la figura en grupos tal que en todo grupo se pueda viajar desde cualquier punto a cualquier otro siguiendo sólo los segmentos marcados, pero es imposible viajar desde un punto de un grupo a un punto de otro grupo distinto. Llamamos nivel a la cantidad de estos grupos.
Notemos que en cada jugada, el jugador puede o bien no modificar el nivel o bien bajar el nivel en $1$ (cuando conecta dos grupos con un segmento). De este modo, el nivel empieza en $n$ y decrece uno en uno para terminar en $1$.
Por otro lado, veamos que un grupo puede ser o bien un grupo central si contiene al centro del polígono, o bien un grupo periférico, si no lo contiene. Es claro que hay un único grupo central y vamos a denotar por $c$ a la cantidad de puntos que tiene sin contar el centro.
Además, notemos que podemos dividir a los vértices del polígono en grupos de consecutivos en el mismo grupo (posiblemente el central). Digamos que hay $k$ de estos grupos.
Ahora sí, vamos a definir la potencia del juego en un momento como
$$P = n - k + c$$
Notemos que la potencia equivale a, dado un juego cualquiera, la cantidad máxima de segmentos que puede haber al final si se juega exclusivamente sin bajar el nivel (la forma de ver esto es simple: Fijémonos que la cantidad total de segmentos que podemos trazar sin bajar el nivel son los que unen al centro con los vértices en el grupo central, que son $c$, y los segmentos que unen a vértices consecutivos en el mismo grupo, que, recordando la definición de $k$, son $n-k$).
Para simplificar la solución, vamos a asignar a Ana la paridad “impar” y a Beto la paridad “par”. En un juego con algún $n$, llamaremos por $X$ al jugador cuya paridad coincide con $n$ y por $Y$ al otro jugador. Queremos probar que $X$ puede asegurarse ganar.
Notemos que al principio del juego, el nivel y la potencia son $n+1$ y $0$, respectivamente. Vamos a probar que $X$ puede asegurarse de que en cada vez que le toca jugar a $Y$, el nivel sea impar y que la potencia tenga la misma paridad que $n$:
Vamos a hacer una inducción. Al principio ya sabemos que el nivel y la potencia son $n+1$ y $0$. Si $n$ es par entonces Ana, que es $Y$, tiene un juego con nivel $n+1$, que es impar y potencia $0$, que es par*. Ahora, si $n$ es impar, entonces Ana, que es $X$, puede conectar un vértice con el centro y el nivel sería $n$, que es impar y la potencia sería $1$, que tiene la misma paridad que $n$, impar.
Ahora supongamos que $Y$ recibe un juego con nivel impar y potencia de paridad igual a $n$ y realiza una jugada cualquiera. Esta puede ser de dostipos:
Jugada a: El nivel no decrece, al conectarse dos puntos en el mismo grupo:
Notemos que haciendo esto, la potencia no decreció (ya que no cambió ninguno de los grupos). De este modo, como la potencia tiene la paridad de $X$, por definición de potencia, $X$ va a poder poner algún segmento sin bajar el nivel. Entonces, en ningún momento el nivel o la potencia cambiaron así que el paso inductivo se cumple.
Jugada b: El nivel decrece en $1$, al conectarse dos grupos. Acá tenemos otros dos casos:
Caso i: El grupo central contiene únicamente al centro:
Si este caso se da, entonces es claro que la jugada de $Y$ sólo pudo ser una que conectaba dos grupos periféricos. De este modo, al hacer su jugada, $Y$ disminuyó la potencia en $1$, por lo que basta con disminuirla en otro número impar. Para hacerlo, basta con que $X$ conecte otros dos grupos periféricos.
Caso ii: El grupo central contiene a al menos un vértice:
En este caso, tomemos un vértice del grupo central tal que a alguno de sus lados haya un vértice de un grupo periférico. Supongamos que este último tiene tamaño $t$. Notemos que $X$ puede conectarlo al central de dos maneras: puede conectar algún vértice de este grupo al centro, aumentando la potencia en $t$ o puede conectar el vértice del extremo de este grupo al vértice en el grupo central aumentando la potencia en $t+1$ (dado que $c$ aumenta en $x$ y $k$ disminuye en $1$). En ambos casos, el nivel disminuye en $1$, por lo que el nivel final vuelve a ser impar. Con respecto a la potencia, como $x$ y $x+1$ tienen distintas paridades, simplemente tomamos el caso en el que la potencia resultante es la deseada.
Si $X$ juega de esta forma, $Y$ siempre recibe un juego con nivel impar. De esto, podemos deducir que si en algún momento el juego pasa de nivel $4$ a nivel $3$, entonces es en la jugada de $X$. De este modo, cuando el juego entre a nivel $3$, podemos estar seguros de que la potencia tendrá la misma paridad que $n$ (porque acaba de jugar $X$). Ahora bien, si algún jugador disminuyera el nivel a $2$, entonces el otro lo bajaría a $1$ y ganaría. Pero por otro lado, por definición de potencia, el jugador que coloca el segmento número $P+1$ está obligado a bajar el nivel (y las jugadas anteriores pueden hacerse sin bajar el nivel). Y como $P+1$ tiene la paridad de $Y$, este último es quien coloca ese segmento y por ende quien pierde.
Como se ve que los argumentos generales no me funcionan, vamos a dividir el problema en $n$ par e impar.
Para $n$ par, vamos a describir una estrategia ganadora para Beto (una que muchos propusieron en la prueba): la estrategia de Beto es jugar simétrico, hasta que tiene oportunidad de ganar (i.e. quedan solo 2 regiones conexas), en cuyo caso simplemente hace el movimiento que le lleva a la victoria. No voy a abundar en detalles, pero no es muy difícil ver que esto funciona.
Ahora viene lo interesante... vamos a ver que para el caso $n$ impar, Ana tiene una estrategia ganadora:
El primer paso de su estrategia va a ser siempre conectar un vértice, digamos $V$ con el centro $O$ del polígono... No es difícil ver que para $n=3$ esto lleva a una estrategia ganadora: la estrategia es fácil, Beto está obligado a trazar un segmento que conecte dos regiones conexas que antes no estaban conectadas, haciendo que Ana reciba exactamente dos regiones conexas distintas, por lo que puede unirlas y gana.
Ahora, vamos a construir su estrategia ganadora para $n>3$ a partir de valores de $n$ más chiquitos. Notemos que Beto en su turno puede hacer dos cosas:
Puede trazar un lado, digamos $AB$. En caso de que haga esto, la estrategia de Ana siempre va a ser trazar un lado consecutivo, digamos $BC$. De este modo, si nos fijamos los tres vértices $A$, $B$, $C$, podemos imaginarnos que en realidad forman "un único vértice" $P$. Esto se puede ver dado que los movimientos posibles son dos: puede conectar $A$ o $C$ a uno de sus vértices adyacentes que no son $B$, que sería análogo a conectar $V$ con este vértice adyacente; o bien puede conectar $A$, $B$ o $C$ al centro $O$, lo que sería análogo a conectar $P$ con $O$. Lo que después podría pasar es que Beto por segunda vez otro de los vértices $A$, $B$, $C$ al centro, lo cual no afectaría al juego imaginario con $P$, pero entonces Ana puede responder conectando el tercero, lo cual tampoco afectaría al juego imaginario, así que acá no hay ningún problema. (Lo que quiero decir es que después de esta jugada, Ana puede imaginarse que empieza a aplicar su estrategia para $n-2$ y entonces ganaría)
Puede conectar un vértice con el centro, digamos $AO$. Entonces, notemos que el camino $AOV$ ($V$ era el vértice que usaba Ana en su primer jugada) divide al polígono en dos partes. Ahora, yo digo que cada una puede representarse como otro juego para un polígono con menos lados, de la siguiente forma: tomemos alguna de las dos partes, y contemos la cantidad de lados que contiene, llamémosla $l$. Como $A$ y $V$ están conectados, vamos a representarlos por un único vértice $P$, que está conectado al centro $O$. Entonces, los $l$ lados que contiene representarán los $l$ lados de un polígono que tiene como vértices a $P$ y a los otros $l-1$ puntos de la parte que tomamos, cuyo centro también es $O$. Entonces, notemos que otra vez tenemos jugadas correspondientes: conectar uno de los lados de la parte es lo mismo que conectar uno de los lados del polígono imaginario, y conectar alguno de los $l-1$ vértices de la parte al centro es lo mismo que conectar uno de los vértices del polígono imaginario a su centro. Pero bueno, lo único que nos falta notar es que como lo que nos importa es la cantidad de laditos en cada parte, como la cantidad total de lados es impar, resulta ser que uno de los polígonos tiene cantidad impar de lados y otro cantidad impar. En el que tiene cantidad impar, notemos que ya tenemos un vértice conectado al centro (como dijimos que siempre iba a ser la primer jugada de Ana), así que en ese polígono Ana puede aplicar su estrategia ganadora para impar ni bien Beto haga su primer movimiento en este polígono y entonces ganar. Ahora, el polígono con cantidad de lados par, ya tenemos un vértice y el centro conectados... pero sabíamos que para este polígono "Beto", el segundo jugador", tenía estrategia ganadora... así que Ana puede imaginarse que este segmento ya trazado corresponde a una jugada de Ana y puede hacerse pasar por "Beto" y responder acordemente (acá por fin terminó de usar su turno). Entonces, en esta situación tiene dos polígonos en los cuales ocupa el lugar del jugador con estrategia ganadora, así que si responde en cada uno acordemente cuando Beto juega, podrá asegurarse que en cada polígono individualmente, ella sea la jugadora que haga que todos los vértices queden conectados. Y bueno, para que todos los vértices del polígono original queden conectados precisamos que todos los vértices de AMBOS polígonos estén conectados, así que Ana tiene la estrategia ganadora.
Falta rellenar un poco los detalles pero me parece que con esto SÍ estaríamos (de hecho, debería funcionar también para $n$ par pero habría que aclarar unas cositas dependiendo de si los polígonos quedan par-par o impar-impar).
PD: la solución debería poder narrarse sin inducción, dado que podemos reemplazar la parte de "usa su estrategia para $n-2$ por la estrategia concreta... En definitiva creo que quedaría algo como: cada vez que Beto parte el polígono en dos, se fija el polígono par y juega simétrico en él, mientras que en el polígono impar se queda atenta a una nueva partición por parte de Beto (y mientras Beto no conecte nada al centro, sigue agregando laditos).
