Q5 Matemática  (Cono Sur Olympiad 1998)

Na Terra Brasilis existem $n$ casas onde moram $n$ goblins, cada um em uma casa. Existem rotas de sentido único tais que: - cada rota une duas casas, - em cada casa começa exatamente uma rota, - em cada casa termina exatamente uma rota. Se uma rota vai da casa $A$ até a casa $B$, então diremos que a casa $B$ fica ao lado da casa $A$. Essa relação não é simétrica, ou seja: nesta situação, não necessariamente a casa $A$ está ao lado da casa $B$. Todos os dias, a partir do dia $1$, cada goblin sai da casa onde está e chega na próxima casa. Uma lenda da Terra Brasilis diz que quando todos os goblins retornarem à posição original, o mundo acabará. a) Mostre que o mundo vai acabar. b) Se $n=98$, mostre que é possível para os elfos construir e guiar as rotas para que o mundo não acabe antes de $300.000$ anos.