Combinatoria
2016 Iominternational Olympiad Of Metropolises (2016)

2016 Iominternational Olympiad Of Metropolises P6

En un país con $n$ ciudades, algunos pares de ciudades están conectados por vuelos de ida operados por una de dos compañías $A$ y $B$. Dos ciudades pueden estar conectadas por más de un vuelo en cualquier dirección. Una palabra $AB$ $w$ se denomina implementable si existe una sucesión de vuelos conectados cuyos nombres de compañía forman la palabra $w$. Dado que toda palabra $AB$ de longitud $2^n$ es implementable, demuestre que toda palabra $AB$ finita es implementable. (Una palabra $AB$ de longitud $k$ es una secuencia arbitraria de $k$ letras $A$ o $B$; por ejemplo, $AABA$ es una palabra de longitud $4$).

También aparece como:Iom 2016 Problema 6

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados