## APMO 2016 #4

### APMO 2016 #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.

- nahin munkar
**Posts:**81**Joined:**Mon Aug 17, 2015 6:51 pm**Location:**banasree,dhaka

### Re: APMO 2016 #4

I think, the answer is $57$.(may be).

According to condition, we can make a cycle of $57$ cities where it is always possible to have a reach-connection between any two cities using at most $28$ flights . So,any $2$ of those $57$ cities cannot situate in the same group. So, at least $57$ groups are needed so that the condition holds. For this, $k=57$.

According to condition, we can make a cycle of $57$ cities where it is always possible to have a reach-connection between any two cities using at most $28$ flights . So,any $2$ of those $57$ cities cannot situate in the same group. So, at least $57$ groups are needed so that the condition holds. For this, $k=57$.

**# Mathematicians stand on each other's shoulders**.

*~ Carl Friedrich Gauss*

- asif e elahi
**Posts:**183**Joined:**Mon Aug 05, 2013 12:36 pm**Location:**Sylhet,Bangladesh

### Re: APMO 2016 #4

But you have to prove that it's always possible to put them in $57$ groups. Here is a hint.nahin munkar wrote:I think, the answer is $57$.(may be).

According to condition, we can make a cycle of $57$ cities where it is always possible to have a reach-connection between any two cities using at most $28$ flights . So,any $2$ of those $57$ cities cannot situate in the same group. So, at least $57$ groups are needed so that the condition holds. For this, $k=57$.