XI Torneo de las ciudades Otoño 2018 Norte-Nivel Juvenil Problema 7

Problemas que aparecen en el Archivo de Enunciados.
Sandy

OFO - Medalla de Bronce
Mensajes: 50
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 1
Nivel: 2

XI Torneo de las ciudades Otoño 2018 Norte-Nivel Juvenil Problema 7

Mensaje sin leer por Sandy » Mar 13 Nov, 2018 10:05 pm

En un mundo virtual hay $n\geq 2$ ciudades. Algunos pares de ciudades están conectadas por caminos (entre dos ciudades hay como máximo un camino). Recorriendo estos caminos, es posible llegar a cualquier ciudad desde cualquier otra. Sólo se puede cambiar de un camino a otro cuando se llega a una ciudad. El mundo se llama simple si es imposible salir de una ciudad y regresar a la misma sin pasar dos veces por un mismo camino. De no ser así, el mundo se denomina complicado.
Ana y Beto juegan al siguiente juego. Al comienzo, Ana elige una única dirección en cada camino de modo que el camino sólo pueda ser recorrido en esa dirección, y ubica un turista en una de las ciudades. En cada turno, Ana mueve al turista a lo largo de un camino en la dirección permitida hasta una ciudad vecina. En su turno, Beto cambia la dirección permitida de un camino que sale de- o llega a la ciudad donde se encuentra el turista en ese momento. Beto gana si en algún momento Ana no puede hacer una movida.
Demostrar que
a) En un mundo simple, Ana puede evitar perder, sin importar cómo juegue Beto.
b) En un mundo complicado, Beto puede garantizar su victoria, sin importar cómo juegue Ana.

BrunZo

OFO - Medalla de Bronce FOFO 8 años - Mención Especial OFO - Medalla de Plata FOFO Pascua 2019 - Medalla
Mensajes: 143
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 4
Nivel: 1

Re: XI Torneo de las ciudades Otoño 2018 Norte-Nivel Juvenil Problema 7

Mensaje sin leer por BrunZo » Lun 10 Jun, 2019 7:17 pm

Solución: (botánica)
Spoiler: mostrar
Interpretemos el problema como un grafo.
Es claro que una ciudad es simple o compleja dependiendo de si el grafo es un árbol o si tiene ciclos (respectivamente).

Parte a.
El grafo en cuestión es un árbol.
Tomamos un nodo raíz $N$ y colocamos las direcciones de modo que todos los caminos conduzcan a $N$, excepto una de sus aristas adyacentes. Ahora, Ana coloca al turista en el nodo $N$, y para comenzar, lo mueve en la dirección de la arista que sale de $N$, cayendo en el nodo $M$. Ahora, Beto deberá cambiar una de las aristas adyacentes a $M$, pero por la construcción del grafo, todas ellas apuntan a $M$. Esto es, luego de la movida de Beto, las aristas adyacentes a $M$ apuntarán todas a $M$ excepto una.
Ahora, notemos lo siguiente: tenemos dos grupos de nodos, los que para llegar a ellos (desde $N$) tenés que cruzar por $M$ (la "rama" de $M$) y las otras ramas del árbol. Por construcción del grafo, todos las aristas de la rama $M$ conducen hacia $M$, puesto que se acercan a $N$ (excepto la arista cambiada por Beto), y todos las aristas de las otras ramas, conducen hacia $N$, y como una arista conduce de $N$ a $M$, en consecuencia conducen a $M$. Esto es, todas las aristas del grafo conducen a $M$ excepto una, que es la que Beto cambió. Notemos que esta es exactamente la misma situación que la del principio, de modo que si Ana repite el procedimiento, va a poder moverse infinitamente, evitando perder, como queríamos que pase.

Parte b.
El grafo en cuestión tiene un ciclo.
Supongamos que Ana empieza en un nodo $N$. Es claro que, o bien $N$ pertenece al ciclo, o bien pertenece a un subgrafo que sea un árbol que contenga un nodo del ciclo. Hagamos de cuenta que este árbol tiene raíz en $N$.
Para empezar, hacemos lo siguiente: Si Ana se mueve a un nodo mediante una arista, cambiamos cualquier arista diferente a la que pasó Ana, excepto que Ana se mueva a una "hoja" (nodo con una sola arista), caso en el que cambiamos esa arista y hacemos a Ana regresar al punto de partida. Notemos que, por la serie de movimientos que hacemos, Ana nunca va a poder pasar por el mismo nodo dos veces, y como no hay infinitos nodos, o bien Ana llega al ciclo, o bien pierde en el camino.
Ahora dentro del ciclo, vamos a seguir el procedimiento con un agregado: Si desde la arista en la que esta el turista existe alguna arista que puede llevar afuera del ciclo, cambiamos esa (siempre y cuando la dirección lleve a salir del ciclo). Como estamos en un ciclo, en cada nodo siempre va a haber al menos dos aristas (no hay hojas), por lo que siempre podremos cambiar una arista distinta a la que usó Ana, y como antes, siempre podremos evitar que Ana pase dos veces por el mismo nodo. Para finalizar, notemos que por la forma del ciclo, obligaremos a Ana a dar la vuelta alrededor de todo el ciclo, haciendo que las aristas queden todas apuntando a la misma dirección (horaria o antihoraria). Entonces, cuando volvamos a la arista primera del ciclo, Beto puede cambiar la arista que sale del ciclo y ganar, como queríamos.
2  

Responder