HMMT 二月 2005 · 冲刺赛 · 第 41 题

英文解析

41. There are 42 stepping stones in a pond, arranged along a circle. You are standingon one of the stones. You would like to jump among the stones so that you movecounterclockwise by either 1 stone or 7 stones at each jump. Moreover, you would liketo do this in such a way that you visit each stone (except for the starting spot) exactlyonce before returning to your initial stone for the first time. In how many ways canyou do this?
    Solution: 63
    Number the stones 0 , 1 , . . . , 41, treating the numbers as values modulo 42, and let rnbe the length of your jump from stone n . If you jump from stone n to n + 7, then youcannot jump from stone n + 6 to n + 7 and so must jump from n + 6 to n + 13. Thatis, if r = 7, then r = 7 also. It follows that the 7 values r , r , r , . . . , rn n +6 n n +6 n +12 n +36
    are all equal: if one of them is 7, then by the preceding argument applied repeatedly,
    all of them must be 7, and otherwise all of them are 1. Now, for n = 0 , 1 , 2 , . . . , 42,
    let s be the stone you are on after n jumps. Then s = s + r , and we haven n +1 n ss = s + r ≡ s + 1 (mod 6). By induction, s ≡ s + i (mod 6); in particularnn +1 n s n n + i n
    16 ns ≡ s , so r = r . That is, the sequence of jump lengths is periodic with periodn +6 n s +6 sn n
    6 and so is uniquely determined by the first 6 jumps. So this gives us at most 2 = 646
    possible sequences of jumps r , r , . . . , r .
    s s s
    0 1 41
    Now, the condition that you visit each stone exactly once before returning to theoriginal stone just means that s , s , . . . , s are distinct and s = s . If all jumps are
    0 1 41 42 0
    length 7, then s = s , so this cannot happen. On the other hand, if the jumps are not
    6 0
    all of length 7, then we claim s , . . . , s are indeed all distinct. Indeed, suppose s = s
    0 41 i jfor some 0 ≤ i < j < 42. Since s ≡ s + ( j − i ) (mod 6), we have j ≡ i (mod 6), soj ij − i = 6 k for some k . Moreover, since the sequence of jump lengths has period 6, wehaves − s = s − s = · · · = s − s .
    i +6 i i +12 i +6 i +6 k i +6( k − 1)
    Calling this common value l , we have kl ≡ 0 mod 42. But l is divisible by 6, andj − i < 42 ⇒ k < 7 means that k is not divisible by 7, so l must be. So l , the sum ofsix successive jump lengths, is divisible by 42. Hence the jumps must all be of length
    7, as claimed.
    This shows that, for the 64 − 1 = 63 sequences of jumps that have period 6 and are notall of length 7, you do indeed reach every stone once before returning to the startingpoint.