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 4 of 4: Remove and reinsert

v

Previous step Next step

\deg^-(v)\le28,\ \deg^+(v)\le28 \implies v \text{ has} \le56 \text{ neighbours}

Detailed analysis

Remove $v$ ; by the inductive hypothesis the remaining graph splits into at most $57$ valid groups. Vertex $v$ has in-degree and out-degree each at most $28$ in the original graph, so it is adjacent to at most $56$ other vertices, occupying at most $56$ of the $57$ groups. Hence some group contains none of its neighbors, and $v$ can be placed there, completing the induction. Therefore $57$ groups always suffice, so $k=57$ .