## APMO 2016 #4

Discussion on Asian Pacific Mathematical Olympiad (APMO)
Posts: 90
Joined: Fri Dec 28, 2012 8:35 pm

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

asif e elahi
Posts: 183
Joined: Mon Aug 05, 2013 12:36 pm