PUMaC 2014 · 数论（B 组） · 第 7 题

PUMaC 2014 — Number Theory (Division B) — Problem 7

[ 7 ] How many permutations p ( n ) of { 1 , 2 , 3 ... 35 } satisfy a | b implies p ( a ) | p ( b )?

解析

[ 7 ] How many permutations p ( n ) of { 1 , 2 , 3 ... 35 } satisfy a | b implies p ( a ) | p ( b )? Solution: We look at small numbers first. It is not hard to reason that 1, 2, 3, 4, and 5 must be fixed, since there are no other numbers that have 35, 17, 11, 8 and 7 divisors in the set. Similarly, 6, 7, 8, 9, 10, 11, and 12 are also fixed (even though 9 and 10 both have 3 divisors in the set, the fact that 1 through 5 are fixed makes them fixed as well). From 13 through 17, all of them have 2 divisors in the set. 14, 15 and 16 are fixed due to the fact that 7, 5, and 8 are fixed. Thus, the only possible move is to switch 13 and 17. From 18 through 35, the primes 19, 23, 29, and 31 can switch positions between themselves and everything else is fixed (since they can all be decomposed into smaller factors that are already fixed). Therefore, there are a total of 4! × 2 = 48 possible permutations.