HMMT 二月 2004 · 冲刺赛 · 第 39 题

HMMT February 2004 — Guts Round — Problem 39

[15] You want to arrange the numbers 1 , 2 , 3 , . . . , 25 in a sequence with the following property: if n is divisible by m , then the n th number is divisible by the m th number. How many such sequences are there? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HARVARD-MIT MATHEMATICS TOURNAMENT, FEBRUARY 28, 2004 — GUTS ROUND

解析

You want to arrange the numbers 1 , 2 , 3 , . . . , 25 in a sequence with the following prop- erty: if n is divisible by m , then the n th number is divisible by the m th number. How many such sequences are there? Solution: 24 Let the rearranged numbers be a , . . . , a . The number of pairs ( n, m ) with n | m 1 25 must equal the number of pairs with a | a , but since each pair of the former type n m is also of the latter type, the converse must be true as well. Thus, n | m if and only if a | a . Now for each n = 1 , 2 , . . . , 6, the number of values divisible by n uniquely n m determines n , so n = a . Similarly, 7 , 8 must either be kept fixed by the rearrangement n or interchanged, because they are the only values that divide exactly 2 other numbers in the sequence; since 7 is prime and 8 is not, we conclude they are kept fixed. Then we can easily check by induction that n = a for all larger composite numbers n ≤ 25 (by n using m = a for all proper factors m of n ) and n = 11 (because it is the only prime m that divides exactly 1 other number). So we have only the primes n = 13 , 17 , 19 , 23 left to rearrange, and it is easily seen that these can be permuted arbitrarily, leaving 4! possible orderings altogether.