Library / /34 of 49

, 2022

Combinatorics Difficulty 6.6 National Olympiad Prove it Bulgaria

There are $n$ towns in a country. Some of the towns are connected with one way roads and between any two towns it is possible to have several roads in both directions. It is known that for any two towns $A$ and $B$ one can travel from $A$ to $B$ , or from $B$ to $A$ or both. Find the minimum number of roads that have to be built such that one can travel in both directions between any two towns.

Solution

We prove that the answer is $1$ . Consider towns numbered from $1$ to $n$ and let from town $i$ there is a road to town $i+1$ , $\forall i < n$ . Obviously the condition is fulfilled and we need at least one new road, thus the answer is greater than $0$ .

We show that there is a town $F$ from which one can travel to all other towns. For every town consider the number of towns that can be visited from this town. Choose a town $A$ for which this number is the greatest. There exists a town $B$ such that one can not travel from $A$ to $B$ . According to the condition of the problem one can travel from $B$ to $A$ and consequently to all towns starting from $A$ . This contradicts the maximality of $A$ .

By analogy there exists a town $L$ that is reachable from all other towns. Therefore an edge from $L$ to $F$ satisfies the condition of the problem.

Want a route through all this instead of 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 reproduced verbatim; metadata (topic, difficulty) added by this project.