PUMaC 2016 · 团队赛 · 第 5 题

PUMaC 2016 — Team Round — Problem 5

(4) An alphabet A has 16 letters. A message is written using the alphabet and, to encrypt the message, a permutation f : A → A is applied to each letter. Let n ( f ) be the smallest positive integer k such that every message m , encrypted by applying f to the message k times, produces m . Compute the largest possible value of n ( f ).

解析

Write f in cycle form. Then n ( f ) is the least common multiple of the cycle lengths. The cycle lengths add up to 16. Observe that powers of primes are the most efficient, because any non-power-of-primes can be split into its prime-power components. We do casework by largest cycle length: • 13 = ⇒ 13 · 3 = 39 is the largest possible n ( f ). • 11 = ⇒ 11 · 3 · 2 = 66. • 9 = ⇒ 9 · 2 · 5 = 90. • 8 = ⇒ 8 · 3 · 5 = 120. • 7 = ⇒ 7 · 5 · 4 = 140. So the maximum is 140 . Problem written by Eric Neyman. 1