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:185
- 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$.