Q6 Matemática  (International Olympiad of Metropolises 2016)

Em um país com $n$ cidades, alguns pares de cidades são conectados por voos de ida operados por uma das duas companhias $A$ e $B$. Duas cidades podem ser conectadas por mais de um voo em qualquer direção. Uma palavra $AB$ $w$ é chamada implementável se houver uma sequência de voos conectados cujos nomes de companhias formam a palavra $w$. Dado que toda palavra $AB$ de comprimento $2^n$ é implementável, prove que toda palavra finita $AB$ é implementável. (Uma palavra $AB$ de comprimento $k$ é uma sequência arbitrária de $k$ letras $A$ ou $B$; por exemplo, $AABA$ é uma palavra de comprimento $4$.)