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 2 of 4: Auxiliary graph of short reachability

Previous step Next step

H:\ u\to v \iff v \text{ reaches } u \text{ in} \le28 \text{ flights},\quad \deg^+_H\le28

Detailed analysis

To show $57$ groups always suffice, build an auxiliary directed graph $H$ on the same $2016$ cities with an edge from $u$ to $v$ whenever $u$ is reachable from $v$ using at most $28$ flights in $G$ . Since $G$ has out-degree $1$ everywhere, each vertex has at most $28$ out-neighbors in $H$ (one for each flight-count from $1$ to $28$ ). Partitioning the cities into $57$ groups with no $H$ -edge inside a group solves the original problem.