Maths Olympiad Prep

Library / /216 of 377

Number theory Difficulty 5.2 AIME, harder Find the answer United States

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?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:
Number the stones 0,1,,410, 1, \ldots, 41, treating the numbers as values modulo 4242, and let rnr_n be the length of your jump from stone nn. If you jump from stone nn to n+7n+7, then you cannot jump from stone n+6n+6 to n+7n+7 and so must jump from n+6n+6 to n+13n+13. That is, if rn=7r_n = 7, then rn+6=7r_{n+6} = 7 also. It follows that the 7 values rn,rn+6,rn+12,,rn+36r_n, r_{n+6}, r_{n+12}, \ldots, r_{n+36} are all equal: if one of them is 77, then by the preceding argument applied repeatedly, all of them must be 77, and otherwise all of them are 11.

Now, for n=0,1,2,,42n = 0, 1, 2, \ldots, 42, let sns_n be the stone you are on after nn jumps. Then sn+1=sn+rsns_{n+1} = s_n + r_{s_n}, and we have sn+1=sn+rsnsn+1(mod6)s_{n+1} = s_n + r_{s_n} \equiv s_n + 1 \pmod{6}. By induction, sn+isn+i(mod6)s_{n+i} \equiv s_n + i \pmod{6}; in particular sn+6sns_{n+6} \equiv s_n, so rsn+6=rsnr_{s_n+6} = r_{s_n}. That is, the sequence of jump lengths is periodic with period 66 and so is uniquely determined by the first 66 jumps. So this gives us at most 26=642^6 = 64 possible sequences of jumps rs0,rs1,,rs41r_{s_0}, r_{s_1}, \ldots, r_{s_{41}}.

Now, the condition that you visit each stone exactly once before returning to the original stone just means that s0,s1,,s41s_0, s_1, \ldots, s_{41} are distinct and s42=s0s_{42} = s_0. If all jumps are length 77, then s6=s0s_6 = s_0, so this cannot happen. On the other hand, if the jumps are not all of length 77, then we claim s0,,s41s_0, \ldots, s_{41} are indeed all distinct. Indeed, suppose si=sjs_i = s_j for some 0i<j<420 \leq i < j < 42. Since sjsi+(ji)(mod6)s_j \equiv s_i + (j-i) \pmod{6}, we have ji(mod6)j \equiv i \pmod{6}, so ji=6kj-i = 6k for some kk. Moreover, since the sequence of jump lengths has period 66, we have
si+6si=si+12si+6==si+6ksi+6(k1) s_{i+6} - s_i = s_{i+12} - s_{i+6} = \cdots = s_{i+6k} - s_{i+6(k-1)}
Calling this common value ll, we have kl0(mod42)k l \equiv 0 \pmod{42}. But ll is divisible by 66, and ji<42k<7j-i < 42 \Rightarrow k < 7 means that kk is not divisible by 77, so ll must be. So ll, the sum of six successive jump lengths, is divisible by 4242. Hence the jumps must all be of length 77, as claimed.

This shows that, for the 641=6364-1=63 sequences of jumps that have period 66 and are not all of length 77, you do indeed reach every stone once before returning to the starting point.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.