FOFO de Pascua 2019 Problema E: Alerta meteorológica

Problemas que aparecen en el Archivo de Enunciados.
jujumas

OFO - Mención OFO - Medalla de Plata FOFO 7 años - Medalla Especial OFO - Oro perfecto FOFO Pascua 2017 - Medalla
OFO - Medalla de Oro FOFO 8 años - Jurado OFO - Jurado FOFO Pascua 2019 - Jurado
Mensajes: 383
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 10
Nivel: 2

FOFO de Pascua 2019 Problema E: Alerta meteorológica

Mensaje sin leer por jujumas » Mié 17 Abr, 2019 11:59 pm

En el Río de la Plata hay $20$ islas ordenadas en una grilla de $5 \times 4$, como en la imagen de abajo.
Imagen

Cada isla tiene un puente que la une con sus islas vecinas, y las islas más cercanas a cada costa tienen puentes hacia la costa en cada lado. Los puentes están representados por segmentos en la figura.

Un día se desató una sudestada, poniendo en peligro a estos preciados puentes. Las fuertes ráfagas de viento rompieron algunos de ellos, posiblemente ninguno o todos.

Determinar de cuántas maneras pueden quedar los puentes inmediatamente después de la sudestada de forma tal que sea todavía posible caminar desde Argentina hacia Uruguay, sólo moviéndose por los puentes del Río de la Plata que todavía siguen en pie.

Alerta meteorológica.png
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.

jujumas

OFO - Mención OFO - Medalla de Plata FOFO 7 años - Medalla Especial OFO - Oro perfecto FOFO Pascua 2017 - Medalla
OFO - Medalla de Oro FOFO 8 años - Jurado OFO - Jurado FOFO Pascua 2019 - Jurado
Mensajes: 383
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 10
Nivel: 2

Re: FOFO de Pascua 2019 Problema E: Alerta meteorológica

Mensaje sin leer por jujumas » Dom 21 Abr, 2019 11:36 pm

Solución oficial:
Spoiler: mostrar
Llamemos $X$ el número que buscamos calcular. que como hay $41$ puentes, existen $2^{41}$ formas en la que los puentes pueden quedar después de la tormenta. Consideremos ahora esta imagen.
FOFO2019ProblemaE.png
Los vértices rojos son las islas originales, numeradas del $1$ al $20$. Las aristas rojas representan los lugares en donde estaban los puentes antes de la sudestada. Los vértices azules representan las secciones del río delimitadas por los puentes, las aristas representan las secciones que se pueden conectar al caerse uno de los puentes originales.

Supongamos que Joacoini quiere lograr navegar con su lancha desde el extremo superior del río al extremo inferior, pero como su lancha es demasiado grande, no puede pasar por abajo de un puente todavía en pie. Llamamos $Y$ a la cantidad de formas en la que los puentes que quedan le permitan a Joacoini pueda lograr su objetivo.

Como el conjunto de vértices y aristas rojos es el conjunto de aristas y vértices azules transformado por una rotación, tenemos que $X=Y$.

Notemos ahora que si podemos caminar desde Argentina hasta Uruguay, al trazar este camino tenemos una línea continua de puentes que divide a los vértices azules en dos regiones distintas, y para moverse Joacoini de cualquier vértice azul de una región a cualquier vértice azul de la otra, tendría que pasar por abajo de un puente, por lo que no puede llegar desde el vértice superior hasta al vértice inferior, ya que estos están en regiones distintas. En conclusión, si podemos ir de Argentina a Uruguay, Joacoini no puede moverse en lancha de arriba a abajo.

Además, si suponemos que Joacoini no puede lograr su objetivo, al considerar el conjunto de todos los vértices azules que Joacoini puede visitar, todas las aristas rojas que bordean el conjunto son puentes todavía en pie, lo que nos marca una forma de caminar desde Argentina a Uruguay.

Luego, podemos ir de Argentina a Uruguay sí y sólo sí Joacoini no puede moverse en lancha de arriba abajo, por lo que $X=2^{41}-Y$.

Sumando las dos ecuaciones, tenemos que $2X=2^{41}$ y que $X=2^{40}$, que es la respuesta al enunciado.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
4  

Avatar de Usuario
Monazo

OFO - Medalla de Plata OFO - Medalla de Oro FOFO Pascua 2019 - Mención
Mensajes: 123
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 3
Nivel: 1

Re: FOFO de Pascua 2019 Problema E: Alerta meteorológica

Mensaje sin leer por Monazo » Dom 12 May, 2019 9:41 pm

Che me parece que le encontré un error a esa solución
Spoiler: mostrar
Joacoini ni a palos sabe navegar
4  

Responder