MathDB
Problems
Contests
International Contests
International Olympiad of Metropolises
2016 IOM
6
6
Part of
2016 IOM
Problems
(1)
International Olympiad of metropolises 2016 P6
Source: International Olympiad of metropolises 2016
9/7/2016
In a country with
n
n
n
cities, some pairs of cities are connected by one-way flights operated by one of two companies
A
A
A
and
B
B
B
. Two cities can be connected by more than one flight in either direction. An
A
B
AB
A
B
-word
w
w
w
is called implementable if there is a sequence of connected flights whose companies’ names form the word
w
w
w
. Given that every
A
B
AB
A
B
-word of length
2
n
2^n
2
n
is implementable, prove that every finite
A
B
AB
A
B
-word is implementable. (An
A
B
AB
A
B
-word of length
k
k
k
is an arbitrary sequence of
k
k
k
letters
A
A
A
or
B
B
B
; e.g.
A
A
B
A
AABA
AA
B
A
is a word of length
4
4
4
.)
combinatorics
IOM