Iranian Mathematical Olympiad

We show that bridges satisfying the problem's conditions can be built no matter what the configuration of the highways is. Throughout the solution we denote the highways by $C_1,C_2,\dots$ and $C_n$ and by $G$ the graph determined by those highways (crossroads are vertices of the graph and highways between two crossroads are edges of the graph).

Lemma. Faces of $G$ can be colored by two colors in a way that the colors of every two adjacent faces is different (Two faces are adjacent if they have an edge in common).

Proof of lemma. We proceed by induction on number of edges of graph $G$. We call a coloring of faces of $G$ satisfying the mentioned property, a good coloring. Suppose that $C$ is the shortest path in $G$ that lies in just one highway and assume $C\subset C_1$. Note that because of minimality, $C$ cannot cross itself, so is a simple curve, therefore dividing the plane into two regions. Now, $C-C_1$ is a closed or maybe an empty curve. Suppose that $H$ is the graph consisting of $C-C_1,C_2,\dots$ and $C_n$. Since the number of edges of $H$ is less than $G$, $H$ has a good coloring according to the induction hypothesis. Now, we add curve $C$ to $H$ and change the color of faces inside $C$. It is very easy to check that this is a good coloring of $G$. The base case is when $G$ is empty. In this case we have only one region which obviously has a good coloring!

Finally consider a good coloring (by colors black and white) for the graph $G$ and an arbitrary orientation for each highway. We have two types of edges. For some edges when we are moving through one (in its specified direction) our right face is white. We call such edges, edges of type 1 and others, edges of type 2. Build a bridge in the way of each edge of type 1. Note that in each crossroad exactly two of the edges are directed into the crossroad and only one of those two is of type 1. Hence our construction do not cause any contradictions.