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

Sandy

OFO - Medalla de Bronce
Mensajes: 26
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.

Responder