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

英文解析

39. 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. Howmany 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 typen mis also of the latter type, the converse must be true as well. Thus, n | m if and onlyif a | a . Now for each n = 1 , 2 , . . . , 6, the number of values divisible by n uniquelyn mdetermines n , so n = a . Similarly, 7 , 8 must either be kept fixed by the rearrangementor interchanged, because they are the only values that divide exactly 2 other numbersnin the sequence; since 7 is prime and 8 is not, we conclude they are kept fixed. Then wecan easily check by induction that n = a for all larger composite numbers n ≤ 25 (bynusing m = a for all proper factors m of n ) and n = 11 (because it is the only primemthat 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.