Baltic Way 1997 · Problem 9

Solution: Answer: yes. For any two given worlds, Gandalf can move between them either in both directions or none. Hence, it suffices to show that Gandalf can move to the world $1$ from any given world $n$. For that, it is sufficient for him to be able to move from any world $n>1$ to some world $m$ such that $m<n$. We consider three possible cases:

a) If $n=3k+1$, then Gandalf can move directly from the world $n$ to the world $k<n$.

b) If $n=3k+2$, then Gandalf can move from the world $n$ to the world $2n=6k+4=3\cdot(2k+1)+1$ and further to the world $2k+1<n$.

c) If $n=3k$ then Gandalf can move from the world $n$ to the world $3n+1=9k+1$, further from there to the worlds $2\cdot(9k+1)=18k+2$, $2\cdot(18k+2)=36k+4=3\cdot(12k+1)+1$, $12k+1$, $4k$ and finally to the world $2k<n$.