MathDB
Problems
Contests
International Contests
Cono Sur Olympiad
1998 Cono Sur Olympiad
5
5
Part of
1998 Cono Sur Olympiad
Problems
(1)
the world will end because of goblins in Terra Brasilis (corrected)
Source: Cono Sur 1998 P5
8/30/2018
In Terra Brasilis there are
n
n
n
houses where
n
n
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
A
A
to house
B
B
B
, then we will say that house
B
B
B
is next to house
A
A
A
. This relationship is not symmetric, that is: in this situation, not necessarily house
A
A
A
is next to house
B
B
B
. Every day, from day
1
1
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
n = 98
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
300,000
300
,
000
years.
combinatorics