n개 도시가 있는 어느 나라가 있다. 어떤 두 도시 사이에는 두 회사 A,B 중 하나가 운항하는 편도 항공편이 있을 수 있다. 두 도시 사이의 항공편은 각 방향으로 여러 편이 있을 수도 있다. 연결된 항공편의 나열에서 회사 이름만 써봤을때 w라는 문자열이 나오면 그 A, B로 구성된 문자열 w를 `구현가능’하다고 하자. 만일 길이가 $2^n$이고 A, B로 구성된 모든 문자열이 구현가능하다면, 유한한 길이이면서 A, B로 구성된 모든 문자열이 구현가능함을 증명하라.