HMMT 二月 2008 · TEAM2 赛 · 第 6 题

英文解析

6. [ 40 ] Suppose that j (0) j (1) · · · j ( n − 1) is a valid juggling sequence. For i = 0 , 1 , . . . , n − 1,
   Let a denote the remainder of j ( i ) + i when divided by n . Prove that ( a , a , . . . , a ) is ai 0 1 n − 1
   permutation of (0 , 1 , . . . , n − 1).
   Solution: Suppose that a = j ( i ) + i − b n , where b is an integer. Note that f ( i − b n ) =
   i i i ii − b n + j ( i ) = a . Since { i − b n | i = 0 , 1 , . . . , n − 1 } contains n distinct integers (as theiri i iresidue mod n are all distinct), and f is a permutation, we see that after applying the mapf , the resulting set { a , a , . . . , a } is a set of n distinct integers. Since 0 ≤ a < n from
   0 1 n − 1 idefinition, we see that ( a , a , . . . , a ) is a permutation of (0 , 1 , . . . , n − 1).
   0 1 n − 1