Problem

Source: Turkey NMO 2007 Problem 6

Tags: combinatorics proposed, combinatorics



In a country between each pair of cities there is at most one direct road. There is a connection (using one or more roads) between any two cities even after the elimination of any given city and all roads incident to this city. We say that the city $A$ can be k -directionally connected to the city $B$, if : we can orient at most $k$ roads such that after arbitrary orientation of remaining roads for any fixed road $l$ (directly connecting two cities) there is a path passing through roads in the direction of their orientation starting at $A$, passing through $l$ and ending at $B$ and visiting each city at most once. Suppose that in a country with $n$ cities, any two cities can be k - directionally connected. What is the minimal value of $k$?