CONO-SUR 1998 Problem 5

In Terra Brasilis there are $n$ houses where $n$ goblins live, each in a house. There are one-way routes such that:

• each route joins two houses,
• in each house exactly one route begins,
• in each house exactly one route ends. If a route goes from house $A$ to house $B$ , then we will say that house $B$ is next to house $A$ . This relationship is not symmetric, that is: in this situation, not necessarily house $A$ is next to house $B$ . Every day, from day $1$ , each goblin leaves the house where he is and arrives at the next house. A legend of Terra Brasilis says that when all the goblins return to the original position, the world will end. a) Show that the world will end. b) If $n = 98$ , show that it is possible for elves to build and guide the routes so that the world does not end before $300,000$ years.