HMMT 二月 2002 · 冲刺赛 · 第 42 题

英文解析

42. Find all the integers n > 1 with the following property: the numbers 1 , 2 , . . . , n can be arranged in a line so that, of any two adjacent numbers, one is divisible by the other.
    Solution: 2 , 3 , 4 , 6 The values n = 2 , 3 , 4 , 6 work, as shown by respective examples
    1 , 2; 2 , 1 , 3; 2 , 4 , 1 , 3; 3 , 6 , 2 , 4 , 1 , 5. We shall show that there are no other possibilities. Ifn = 2 k + 1 is odd, then none of the numbers k + 1 , k + 2 , . . . , 2 k + 1 can divide any other,
    so no two of these numbers are adjacent. This is only possible if they occupy the 1 st, 3 rd,
    . . . , (2 k + 1)th positions in the line, which means every number ≤ k is adjacent to two ofthese and hence divides two of them. But k only divides one of these numbers when k ≥ 2.
    Thus no odd n ≥ 5 works. If n = 2 k is even, the numbers k + 1 , k + 2 , . . . , 2 k again must be mutually nonadjacent, but now this means we can have up to two numbers ≤ k each ofwhich is adjacent to only one number > k , and if there are two such numbers, they must be adjacent. If k ≥ 4, then each of k − 1 , k divides only one of the numbers k + 1 , . . . , 2 k ,
    so k − 1 , k must be adjacent, but this is impossible. Thus no even k ≥ 8 works, and we aredone.