AoPS - Problem

Source: Baltic Way 2004, problem 15

Tags: combinatorics unsolved, combinatorics

Megus

20.11.2004 18:18

A circle is divided into $13$ segments, numbered consecutively from $1$ to $13$. Five fleas called $A,B,C,D$ and $E$ are sitting in the segments $1,2,3,4$ and $5$. A flea is allowed to jump to an empty segment five positions away in either direction around the circle. Only one flea jumps at the same time, and two fleas cannot be in the same segment. After some jumps, the fleas are back in the segments $1,2,3,4,5$, but possibly in some other order than they started. Which orders are possible ?

I remember having solved this before the crash. Represent the motion on a circle numbered differently, so that each movement on the initial circle is translated to the second circle as one step (instead of $5$ steps at a time). We number the $13$ segmnents of the new circle in the following way, in a counterclockwise direction: $1,6,11,3,8,13,5,10,2,7,12,4,9$. We can now see that because of the constraint that no two fleas can share a square, the fleas cannot jump over one another, so the only possible permutations are the cyclic permutations, and only those.