FOFO de Pascua 2024 Problema 9

Problemas que aparecen en el Archivo de Enunciados.
BrunZo

OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Copa-FOFO 10 años OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años
OFO - Medalla de Oro-OFO 2022 FOFO Pascua 2022 - Medalla-FOFO Pascua 2022 FOFO 12 años - Medalla-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024 FOFO Pascua 2024 - Jurado-FOFO Pascua 2024
Mensajes: 421
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 17
Nivel: 3

FOFO de Pascua 2024 Problema 9

Mensaje sin leer por BrunZo »

En Argentina hay $n$ ciudades. Algunos pares de ciudades están conectados por vuelos unidireccionales operados por Aerolíneas Argentinas ($A$), por Flybondi ($B$), o por ambas. Dos ciudades pueden ser conectadas por vuelos en ambas direcciones y más de un vuelo por cada dirección.
Una palabra es una sucesión finita de letras $A$ y $B$. La longitud de una palabra es la cantidad total de letras que usa. Una palabra $p$ es implementable si existe una sucesión de vuelos conectados (el destino de cada vuelo tiene que ser el origen del siguiente) cuyas compañías, en orden, forman la palabra $p$.
Suponiendo que toda palabra de longitud $2^n$ es implementable, demostrar que toda palabra de cualquier longitud finita es implementable.
BrunZo

OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Copa-FOFO 10 años OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años
OFO - Medalla de Oro-OFO 2022 FOFO Pascua 2022 - Medalla-FOFO Pascua 2022 FOFO 12 años - Medalla-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024 FOFO Pascua 2024 - Jurado-FOFO Pascua 2024
Mensajes: 421
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 17
Nivel: 3

Re: FOFO de Pascua 2024 Problema 9

Mensaje sin leer por BrunZo »

Aquí publicaremos la solución oficial.
Responder