Álgebra
Iom (2016)
Iom 2016 Problema 6
6 En un país con $n$ ciudades, algunos pares de ciudades están conectados por vuelos de un solo sentido operados por una de dos compañías $A$ y $B$ . Dos ciudades pueden estar conectadas por más de un vuelo en cualquiera de las dos direcciones. Una $AB$ - palabra $w$ se llama implementable si existe una sucesión de vuelos conectados cuyos nombres de compañías forman la palabra $w$ . Dado que toda $AB$ - palabra de longitud $ 2^n $ es implementable, demuestre que toda $AB$ - palabra finita es implementable. (Una $AB$ - palabra de longitud $k$ es una sucesión arbitraria de $k$ letras $A $ o $B$ ; p. ej. $ AABA $ es una palabra de longitud $4$ . )
También aparece como:2016 Iominternational Olympiad Of Metropolises P6
Inicia sesión para agregar soluciones y pistas