HMMT 十一月 2012 · 团队赛 · 第 6 题

HMMT November 2012 — Team Round — Problem 6

[ 6 ] Let π be a permutation of the numbers from 1 through 2012. What is the maximum possible number of integers n with 1 ≤ n ≤ 2011 such that π ( n ) divides π ( n + 1)?

解析

[ 6 ] Let π be a permutation of the numbers from 1 through 2012. What is the maximum possible number of integers n with 1 ≤ n ≤ 2011 such that π ( n ) divides π ( n + 1)? Answer: 1006 Since any proper divisor of n must be less than or equal to n/ 2, none of the numbers greater than 1006 can divide any other number less than or equal to 2012. Since there are at most 1006 values of n for which π ( n ) ≤ 1006, this means that there can be at most 1006 values of n for which π ( n ) divides π ( n + 1). On the other hand, there exists a permutation for which π ( n ) divides π ( n + 1) for exactly 1006 values of n , namely the permutation: 2 3 10 2 3 9 (1 , 2 , 2 , 2 , . . . , 2 , 3 , 2 · 3 , 2 · 3 , 2 · 3 , . . . , 2 · 3 , 5 , . . . ) k Formally, for each odd number ℓ ≤ 2012, we construct the sequence ℓ, 2 ℓ, 4 ℓ, . . . , 2 ℓ , where k is the k largest integer such that 2 ℓ ≤ 2012. We then concatenate all of these sequences to form a permutation of the numbers 1 through ℓ (note that no number occurs in more than one sequence). It follows that if π ( n ) ≤ 1006, then π ( n + 1) will equal 2 π ( n ), and therefore π ( n ) will divide π ( n + 1) for all 1006 values of n satisfying 1 ≤ π ( n ) ≤ 1006.