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.
Problem
Source: Cono Sur 1998 P5
Tags: combinatorics
30.08.2018 15:08
a) In each connected component movement is periodic b) Note that 1+7+16+9+5+11+13+17+19=98 and the terms in the sum are pairwise relatively prime. Construct disjoint cycles with these lengths and the overall period is 1*7*16*9*5*11*13*17*19 = 232792560 > 637000*365.25... so assuming the length of a year remains to be a bit less than 365.25 days ot the end of the world, according to the problem we need more than 637000>300000 years by this construction.
31.08.2018 21:56
The formulation has been updated, as my source's formulation was incomplete (missing a sentence). Thanks to tode for correcting it. In order to save my first formulation, and the first fiven reply, I quote them. parmenides51 wrote: 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. Every day, from day $1$, each goblin leaves the house where he is and arrives at the neighboring 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. stroller wrote: a) In each connected component movement is periodic b) Note that 1+7+16+9+5+11+13+17+19=98 and the terms in the sum are pairwise relatively prime. Construct disjoint cycles with these lengths and the overall period is 1*7*16*9*5*11*13*17*19 = 232792560 > 637000*365.25... so assuming the length of a year remains to be a bit less than 365.25 days ot the end of the world, according to the problem we need more than 637000>300000 years by this construction.
01.09.2018 03:13
I think I actually had interpreted the problem based on the second formulation instead, so it may be a wrong solution to the first version
01.09.2018 04:40
stroller wrote: I think I actually had interpreted the problem based on the second formulation instead, so it may be a wrong solution to the first version Actually it's impossible to work out the first version I think.