APMO 2016 #4

Discussion on Asian Pacific Mathematical Olympiad (APMO)
User avatar
Zawadx
Posts:90
Joined:Fri Dec 28, 2012 8:35 pm
APMO 2016 #4

Unread post by Zawadx » Fri Aug 05, 2016 10:17 am

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.

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

Re: APMO 2016 #4

Unread post by nahin munkar » Fri Aug 05, 2016 4:13 pm

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$. :D
# Mathematicians stand on each other's shoulders. ~ Carl Friedrich Gauss

User avatar
asif e elahi
Posts:185
Joined:Mon Aug 05, 2013 12:36 pm
Location:Sylhet,Bangladesh

Re: APMO 2016 #4

Unread post by asif e elahi » Fri Aug 05, 2016 7:53 pm

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$. :D
But you have to prove that it's always possible to put them in $57$ groups. Here is a hint.
Take a general graph of this kind and find the number of cycles in it.

Post Reply