A town-planner has built an isolated city whose road network consists of $2N$ roundabouts, each connecting exactly three roads. A series of tunnels and bridges ensure that all roads in the town meet only at roundabouts. All roads are two-way, and each roundabout is oriented clockwise.
Vlad has recently passed his driving test, and is nervous about roundabouts. He starts driving from his house, and always takes the first edit at each roundabout he encounters. It turns out his journey incluldes every road in the town in both directions before he arrives back at the starting point in the starting direction. For what values of $N$ is this possible?
I have tried to turn this into an equivalent graph theory problem in which we can apply some results on Euler circuits or similar, but with no such rephrasals seem useful. Any help appreciated!
Best Answer
Partial answer
Let me formalize. If you enter a roundabouts by road $i$ you leave it by road $(i \mod 3) +1$.
Let R.i be the road i of roundabout R.
$N=1$ is a solution of your problem.connect the two roundabout A and B as follow: for all i : A.i is connected to B.i.
We now show that for $N_1,N_2$ solution of your problem then $N_1+N_2+1$ is a solution as well.
Let $T_1,T_2$ be two towA_1s with respectively $2N_1,2N_2$ roundabout. Let $A_1,B_1$ be two roundabout connected in $T_1$ and $A_2,B_2$ connected in $T_2$. We construct a town $T_3$ as follow: we add two roundabout $C$ and $D$ and connect then as follow:
$T_3$ is a solution of your problem with $2N_1+2N_2+2=2(N_1+N_2+1)$ roundabouts.
Thus every odd $N$ is a solution.
@Alex Ravsky comments tells us that $N=2$ is not a solution. So may be Even numbers are impossible (i don't know yet). I'll try to think a a reduction with the same idea in order to prove this