International Olympiad of metropolises 2016 P6
Source: International Olympiad of metropolises 2016
September 7, 2016
combinatoricsIOM
Problem Statement
In a country with cities, some pairs of cities are connected by one-way flights operated by one of two companies and . Two cities can be connected by more than one flight in either direction. An -word is called implementable if there is a sequence of connected flights whose companies’ names form the word . Given that every -word of length is implementable, prove that every finite -word is implementable. (An -word of length is an arbitrary sequence of letters or ; e.g. is a word of length .)