MathDB

4

Part of 2016 APMO

Problems(1)

APMO 2016: one-way flights between cities

Source: APMO 2016, problem 4

5/16/2016
The country Dreamland consists of 20162016 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 kk such that no matter how Starways establishes its flights, the cities can always be partitioned into kk groups so that from any city it is not possible to reach another city in the same group by using at most 2828 flights.
Warut Suksompong, Thailand
combinatoricsAPMO