The localities $P_1, P_2, \dots, P_{1983}$ are served by ten international airlines $A_1,A_2, \dots , A_{10}$. It is noticed that there is direct service (without stops) between any two of these localities and that all airline schedules offer round-trip flights. Prove that at least one of the airlines can offer a round trip with an odd number of landings.
Problem
Source:
Tags: combinatorics, Extremal combinatorics, Ramsey Theory, graph theory, Extremal Graph Theory, IMO Shortlist
sobe86
11.09.2010 20:06
Hint: a graph has no odd cycles if and only if it is bipartite.
exmath89
21.04.2013 07:43
Assume that all airline offers round trips with an even number of landings. Consider a graph with vertices representing the airlines and edges representing a direct service between the two vertices. Each edge is colored with the colors $C_1,C_2,...,C_{10}$, where each color represents a distinct airline.
Since there are no odd cycles of the same color in the graph, the graph is bipartite with respect to each color. Consider the subgraph, $G$, containing all the edges colored $C_1$. The vertices then can be divided into two subgraphs such that no two vertices in the same subgraph share an edge colored $C_1$. By the Pigeonhole Principle, one subgraph contains at least $\lceil 1983/2\rceil=992$ vertices. Let this subgraph be called $G_1$.
Then in $G_1$, consider the edges colored $C_2$. Similarly, we can split the vertices into two groups such that no two vertices in the same group share an edge colored $C_2$. Then one group, $G_2$, contains at least $\lceil 992/2\rceil=496$ vertices.
Continuing in this fashion, $G_3$ contains at least $248$ vertices, $G_4$ contains at least $124$ vertices, $G_5$ contains at least $62$ vertices, $G_6$ contains at least $31$ vertices, $G_7$ contains at least $16$ vertices, $G_8$ contains at least $8$ vertices, $G_9$ contains at least $4$ vertices, and $G_{10}$ contains at least $2$ vertices. But $G_{10}$ contains edges that are not colored with the colors $C_1,C_2,...,C_{10}$ so it must not have any edges at all. But it contains two vertices, and by the problem statement, two vertices must be linked with an edge. Hence, we have a contradiction, so there is one airline that offers a round trip with an odd number of landings. //