Maths Olympiad Prep

Library / Harvard-MIT Mathematics Tournament /201 of 352

Harvard-MIT Mathematics Tournament

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+rsn≡sn+1(mod6)s_{n+1} = s_n + r_{s_n} \equiv s_n + 1 \pmod{6}. By induction, sn+i≡sn+i(mod6)s_{n+i} \equiv s_n + i \pmod{6}; in particular sn+6≡sns_{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 0≤i<j<420 \leq i < j < 42. Since sj≡si+(j−i)(mod6)s_j \equiv s_i + (j-i) \pmod{6}, we have j≡i(mod6)j \equiv i \pmod{6}, so j−i=6kj-i = 6k for some kk. Moreover, since the sequence of jump lengths has period 66, we have
si+6−si=si+12−si+6=⋯=si+6k−si+6(k−1) 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 kl≡0(mod42)k l \equiv 0 \pmod{42}. But ll is divisible by 66, and j−i<42⇒k<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 64−1=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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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