FOFO de Pascua 2019 Problema E: Alerta meteorológica

Problemas que aparecen en el Archivo de Enunciados.
jujumas

OFO - Mención-OFO 2015 OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Oro perfecto-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017
FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
FOFO 9 años - Jurado-FOFO 9 años OFO - Jurado-OFO 2020 COFFEE - Jurado-COFFEE Ariel Zylber
Mensajes: 402
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 13
Nivel: Exolímpico

FOFO de Pascua 2019 Problema E: Alerta meteorológica

Mensaje sin leer por jujumas »

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 2015 OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Oro perfecto-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017
FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
FOFO 9 años - Jurado-FOFO 9 años OFO - Jurado-OFO 2020 COFFEE - Jurado-COFFEE Ariel Zylber
Mensajes: 402
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 13
Nivel: Exolímpico

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

Mensaje sin leer por jujumas »

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.
5  
Avatar de Usuario
Monazo

OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Mención-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
OFO - Jurado-OFO 2023 OFO - Jurado-OFO 2024
Mensajes: 381
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 17
Nivel: Exolímpico

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

Mensaje sin leer por Monazo »

Che me parece que le encontré un error a esa solución
Spoiler: mostrar
Joacoini ni a palos sabe navegar
5  
Soy una Estufa en Piloto
:shock:
Responder