Browse · MathNet
PrintAPMO 2016
2016 counting and probability
Problem
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 such that no matter how Starways establishes its flights, the cities can always be partitioned into groups so that from any city it is not possible to reach another city in the same group by using at most 28 flights.
Solution
The flights established by Starways yield a directed graph on 2016 vertices in which each vertex has out-degree equal to 1.
We first show that we need at least 57 groups. For this, suppose that has a directed cycle of length 57. Then, for any two cities in the cycle, one is reachable from the other using at most 28 flights. So no two cities in the cycle can belong to the same group. Hence, we need at least 57 groups.
We will now show that 57 groups are enough. Consider another auxiliary directed graph in which the vertices are the cities of Dreamland and there is an arrow from city to city if can be reached from using at most 28 flights. Each city has out-degree at most 28. We will be done if we can split the cities of in at most 57 groups such that there are no arrows between vertices of the same group. We prove the following stronger statement.
Lemma: Suppose we have a directed graph on vertices such that each vertex has out-degree at most 28. Then the vertices can be partitioned into 57 groups in such a way that no vertices in the same group are connected by an arrow.
Proof: We apply induction. The result is clear for 1 vertex. Now suppose we have more than one vertex. Since the out-degree of each vertex is at most 28, there is a vertex, say , with in-degree at most 28. If we remove the vertex we obtain a graph with fewer vertices which still satisfies the conditions, so by inductive hypothesis we may split it into at most 57 groups with no adjacent vertices in the same group. Since has in-degree and out-degree at most 28, it has at most 56 neighbors in the original directed graph. Therefore, we may add back and place it in a group in which it has no neighbors. This completes the inductive step.
We first show that we need at least 57 groups. For this, suppose that has a directed cycle of length 57. Then, for any two cities in the cycle, one is reachable from the other using at most 28 flights. So no two cities in the cycle can belong to the same group. Hence, we need at least 57 groups.
We will now show that 57 groups are enough. Consider another auxiliary directed graph in which the vertices are the cities of Dreamland and there is an arrow from city to city if can be reached from using at most 28 flights. Each city has out-degree at most 28. We will be done if we can split the cities of in at most 57 groups such that there are no arrows between vertices of the same group. We prove the following stronger statement.
Lemma: Suppose we have a directed graph on vertices such that each vertex has out-degree at most 28. Then the vertices can be partitioned into 57 groups in such a way that no vertices in the same group are connected by an arrow.
Proof: We apply induction. The result is clear for 1 vertex. Now suppose we have more than one vertex. Since the out-degree of each vertex is at most 28, there is a vertex, say , with in-degree at most 28. If we remove the vertex we obtain a graph with fewer vertices which still satisfies the conditions, so by inductive hypothesis we may split it into at most 57 groups with no adjacent vertices in the same group. Since has in-degree and out-degree at most 28, it has at most 56 neighbors in the original directed graph. Therefore, we may add back and place it in a group in which it has no neighbors. This completes the inductive step.
Final answer
57
Techniques
Graph TheoryColoring schemes, extremal argumentsInduction / smoothing