Problem 4

The country Dreamland consists of

2016

cities. The airline Starways wants to establish some one-way flights between pairs of cities in such a way that each city has exactly one flight out of it. Find the smallest positive integer

k

such that no matter how Starways establishes its flights, the cities can always be partitioned into

k

groups so that from any city it is not possible to reach another city in the same group by using at most

28

flights.

Step 1 of 4: Lower bound from a

57

-cycle

Previous step Next step

k\ge57

Detailed analysis

The flights form a directed graph $G$ on $2016$ vertices in which every vertex has out-degree $1$ . If $G$ contains a directed cycle of length $57$ , then any two cities on this cycle can reach each other using at most $28$ flights (going the shorter way around the $57$ -cycle), so no two of them may share a group. Since Starways can realize such a configuration, at least $57$ groups are always needed, i.e. $k\ge57$ .