Problem:
Five towns are connected by a system of roads. There is exactly one road connecting each pair of towns. Find the number of ways there are to make all the roads one-way in such a way that it is still possible to get from any town to any other town using the roads (possibly passing through other towns on the way).
Solution:
If an assignment of directions for the roads has a town where either all four of its roads are inbound or all four of its roads are outbound, then it is not possible to get from each town to every other town. Conversely, assume all towns have at least one inbound and one outbound road, and suppose it were not possible to get from town to town . Some road is inbound to , so suppose that one can get from to . Some road is outbound from which does not go to either or , so suppose it goes to . Some road is outbound from which does not go to either or , so it must go to the remaining town . Thus no roads from , or can go to , contradicting the assumption that must have at least one inbound road. Therefore if all towns have at least one inbound and one outbound road, it is possible to get from each town to every other town.
It is left to count the number of ways of assigning directions to the roads so that no town has roads that are only inbound or only outbound. There are ways to select directions for all roads. Note that if there is a town where all the roads are outbound, then there is only one such town. To choose an assignment of directions so that one town has only outbound roads, choose one of the towns to have all of its roads outbound, and then assign directions to the other roads in one of ways for a total of ways. Similarly, there are ways to choose an assignment of directions so that one town has only inbound roads. However, some assignments have both a town with only inbound roads and a town with only outbound roads. Choose one town to have only outbound roads in one of ways, choose a second town to have only inbound roads in one of ways, and choose directions for the remaining roads in one of ways, for a total of ways. It follows that there are assignments of directions that result in at least one town having either all outbound or all inbound roads. The requested number is then .