FOFO de Pascua 2024 Problema 9
Este problema en el Archivo de Enunciados:
• Archivo de Enunciados • Competencias de OMAForos • FOFO • Pascua 2024
FOFO de Pascua 2024 Problema 9
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.
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.