HMMT 二月 2008 · TEAM2 赛 · 第 6 题

HMMT February 2008 — TEAM2 Round — Problem 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 a i 0 1 n − 1 permutation of (0 , 1 , . . . , n − 1).

解析

[ 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 a i 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 i i − b n + j ( i ) = a . Since { i − b n | i = 0 , 1 , . . . , n − 1 } contains n distinct integers (as their i i i residue mod n are all distinct), and f is a permutation, we see that after applying the map f , the resulting set { a , a , . . . , a } is a set of n distinct integers. Since 0 ≤ a < n from 0 1 n − 1 i definition, we see that ( a , a , . . . , a ) is a permutation of (0 , 1 , . . . , n − 1). 0 1 n − 1