Problem:
There are 42 stepping stones in a pond, arranged along a circle. You are standing on one of the stones. You would like to jump among the stones so that you move counterclockwise by either 1 stone or 7 stones at each jump. Moreover, you would like to do this in such a way that you visit each stone (except for the starting spot) exactly once before returning to your initial stone for the first time. In how many ways can you do this?
Solution
Solution:
Number the stones , treating the numbers as values modulo , and let be the length of your jump from stone . If you jump from stone to , then you cannot jump from stone to and so must jump from to . That is, if , then also. It follows that the 7 values are all equal: if one of them is , then by the preceding argument applied repeatedly, all of them must be , and otherwise all of them are .
Now, for , let be the stone you are on after jumps. Then , and we have . By induction, ; in particular , so . That is, the sequence of jump lengths is periodic with period and so is uniquely determined by the first jumps. So this gives us at most possible sequences of jumps .
Now, the condition that you visit each stone exactly once before returning to the original stone just means that are distinct and . If all jumps are length , then , so this cannot happen. On the other hand, if the jumps are not all of length , then we claim are indeed all distinct. Indeed, suppose for some . Since , we have , so for some . Moreover, since the sequence of jump lengths has period , we have
Calling this common value , we have . But is divisible by , and means that is not divisible by , so must be. So , the sum of six successive jump lengths, is divisible by . Hence the jumps must all be of length , as claimed.
This shows that, for the sequences of jumps that have period and are not all of length , you do indeed reach every stone once before returning to the starting point.