There are $n$ islands. On each island, I want to install a number of roads (possibly $0$) connecting it to other islands. Each road allows a person to travel in either direction between exactly two islands. I design a network of roads. I ask my friend to build the network for me.
However, my friend mishears and ensures that each road will only carry passengers in one direction i.e. any two islands $a$ and $b$ that share a road, the road will only take passengers from either $a$ to $b$ or $b$ to $a$ (but not both). No matter what plans I give him, he thinks he can always direct the traffic to prevent any travelers from returning to their home island once they have left. Is his claim possible? Prove there is a way that must work, or prove that no such strategy exists.
I was thinking this had to do with graphs, where the graph has to be acyclic to prove his claim, but I'm not sure if this is the case. Maybe, it's possible to prove his claim using Induction? Any help is appreciated.
Your friend always has a strategy. Label the islands by numbers $1,2,\ldots,n$. For a road connecting $i$ and $j$, your friend only has to make the traffic go from $i$ to $j$ if $i<j$, or $j$ to $i$ otherwise. In this way, a traveler can only go from one place to another place with a higher label.