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 3 of 4: Lemma, by induction on the vertex count

Previous step Next step

n\ge1,\ \deg^+\le28 \implies \text{split into } 57 \text{ groups, no internal edge}

Detailed analysis

Lemma: any directed graph on $n\ge1$ vertices with out-degree at most $28$ at every vertex can be split into $57$ groups with no edge inside a group. Proof by induction on $n$ : the base case $n=1$ is trivial. For $n>1$ , the total number of edges is at most $28n$ , so some vertex $v$ has in-degree at most $28$ (otherwise every vertex would have in-degree at least $29$ , giving more than $28n$ edges).