XI Torneo de las ciudades Otoño 2018 Norte-Nivel Juvenil Problema 7
Este problema en el Archivo de Enunciados:
• Archivo de Enunciados • Competencias Internacionales • Torneo de las Ciudades • Torneo de las ciudades 2018-2019 • Octubre 2018 • Nivel JuvenilXI Torneo de las ciudades Otoño 2018 Norte-Nivel Juvenil Problema 7
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.
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.
Fallo inapelable.
Re: XI Torneo de las ciudades Otoño 2018 Norte-Nivel Juvenil Problema 7
Solución: (botánica)