Competition problem — Combinatorics

Library / /26 of 55

Combinatorics Difficulty 5.8 AIME, harder Prove it 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)?

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

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.