I think the original problem wording said all words of length $2^n$ are implementable.

anantmudgal09 wrote: I think the original problem wording said all words of length $2^n$ are implementable. I edited it.

Consider the powerset $P$ of subsets of cities. The size of $S$ is $2^n$. One draws a labeled edge between a set $S$ to a set $T$ labeled '$A$' if $T$ is exactly the set of cities one can reach by starting with a city in $S$ and following a flight from $A$. Likewise with $B$. This makes $P$ into a directed graph. Now, each word $w$ gives us a path in $P$ starting with the set of all cities. The word is implementable if the path does not lead to the empty set. Likewise, each path in $P$ gives us a word $w$. Now, there are $2^n$ elements in $P$, so if there is one can reach the empty set from the set of all cities, the shortest path must be of length at most $2^n-1$. This proves the claim, with the constant $2^n$ shortened to $2^n-1$.

$\textbf{Proof :}$ Consider set of all cities as $S_{\emptyset}$, let set $S_A$ be set of all cities $b$, such that there exists city $a\in S_{\emptyset}$ and where exists way $a\to^{A}b$, like the same define set $S_B$. Next if for some word $w$ with letters $A, B$ we already constructed set $S_w$, then by definition let $S_{wA}$ be set of cities $b$, such that there exists city $a\in S_{w}$ and where exists way $a\to^{A}b$, like the same define set $S_{wB}$. Consider any word $w=ABABBA\ldots A$, let $|w|=2^n+1$ and $w_i$ is first $i$ letters from $w$. There are exactly $2^n$ subsets in set $S_{\emptyset}$, so by Pigeonhole principle there exists two integers $1\leq i< j\leq 2^n+1$, such that $S_{w_i} = S_{w_j}$. So easy to see that for any word $u$, $S_{w_iu} = S_{w_ju}$. So if $w = w_jw'$, then $S_{w} = S_{w_jw'} = S_{w_iw'}$ and $|w_iw'|<|w|=2^n+1$, so $S_{w_iw'}\not=\emptyset$ and $S_{w}\not=\emptyset$. So easy to see that there is realization of word $w$. Same argument holds for any word $w$ with $|w|>2^n$. $\Box$

Wolowizard wrote: 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$.) Take the obvious graph interpretation. Assume the contrary. Let the word $\mathcal W = \omega_1 \omega_2 ... \omega_k$ be the smallest word that is not implementable. Then, consider the set $\mathcal{S}_i$ to be the set of vertices that “form” the word $\omega_1 \omega_2 ... \omega_i$. Note that since we have $k \ge 2^n$, there exist $i, j$ such that $\mathcal{S}_i \equiv \mathcal{S}_j$. Now form the word $\mathcal{W}_0 = \omega_1 \omega_2 ... \omega_i \omega_j \omega_{j+1} ... \omega_k$. Note that $\mathcal{W}_0$ is implementable. Let $\mathcal{V}$ be the last vertex of the path followed by $\mathcal{W}_1 = \omega_1 \omega_2 \omega_3 ... \omega_i$. Note that $\mathcal{V}$ is also the last vertex of the path followed by $\mathcal{W}_2 = \omega_1 \omega_2 \omega_3 ... \omega_j$. But this means that $\mathcal{W}$ is implementable which yields the desired contradiction. $\blacksquare$