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

HMMT February 2002 — Guts Round — Problem 42

[ ± 10] 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. 7

解析

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. If n = 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 1st, 3rd, . . . , (2 k + 1)th positions in the line, which means every number ≤ k is adjacent to two of these 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 of which 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 are done.