Track / Stage 5 / 328 of 400 #1408 of 2444

Problem 1408

AIME late

Combinatorics Difficulty 5.8 Prove it Ukrainian National Mathematical Olympiad · Ukraine

Suppose a country has a system of roads such that the roads intersect in towns only, and do not intersect in-between the towns. Furthermore, from any town one can reach any other town, if one can go in either of the two directions on each road. For no pair of towns, there is more than one direct road connecting them. The government decided to make each road a one-way road, i.e. if towns $A$ and $B$ are connected by a road, then one can use it to get from $A$ to $B$ , or from $B$ to $A$ . Moreover, for each town, there must be at least one road for coming in that town and at least one road for leaving it. Will it always be the case that in this country, there exists a town from which one can get to any other town (even if going through some other towns on the way), or to which one can get from any other town (even if going through some other towns on the way)?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Let us show such system of roads where such town does not exist. Denote by $A, B, C, D$ 3-tuples of towns, where the roads form a cycle, e.g. $A_1 \to A_2 \to A_3 \to A_1$ (fig. 24). In this way, the condition that each town has one incoming and one outcoming road is satisfied. Now, we place additional roads with such directions: $A_1 \to B_1$ , $C_1 \to B_1$ and $C_1 \to D_1$ . Then, one cannot get to any town of groups $A$ and $C$ from other groups, one cannot get to any town in $B$ from group $D$ , and vice versa. Analogously, from any town of any group one cannot get to any town from other groups.

Fig. 24

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.