IOM 2016 Problem 6

In a country with $n$ cities, some pairs of cities are connected by one-way flights operated by one of two companies $A$ and $B$ . Two cities can be connected by more than one flight in either direction. An $AB$ -word $w$ is called implementable if there is a sequence of connected flights whose companies' names form the word $w$ . Given that every $AB$ -word of length $2^n$ is implementable, prove that every finite $AB$ -word is implementable. (An $AB$ -word of length $k$ is an arbitrary sequence of $k$ letters $A$ or $B$ ; e.g. $AABA$ is a word of length $4$ .)