HMMT 十一月 2011 · 冲刺赛 · 第 30 题

英文解析

30. [ 14 ] Let S be a set of consecutive positive integers such that for any integer n in S , the sum of thedigits of n is not a multiple of 11. Determine the largest possible number of elements of S .
    Answer: 38 We claim that the answer is 38. This can be achieved by taking the smallest integerin the set to be 999981. Then, our sums of digits of the integers in the set are
    45 , . . . , 53 , 45 , . . . , 54 , 1 , . . . , 10 , 2 , . . . , 10 ,
    none of which are divisible by 11.
    Suppose now that we can find a larger set S : then we can then take a 39-element subset of S whichhas the same property. Note that this implies that there are consecutive integers a − 1 , a, a + 1 forwhich 10 b, . . . , 10 b + 9 are all in S for b = a − 1 , a, a + 1. Now, let 10 a have sum of digits N . Then, thesums of digits of 10 a + 1 , 10 a + 2 , . . . , 10 a + 9 are N + 1 , N + 2 , . . . , N + 9, respectively, and it followsthat n ≡ 1 (mod 11).
    If the tens digit of 10 a is not 9, note that 10( a + 1) + 9 has sum of digits N + 10, which is divisible by
    11, a contradiction. On the other hand, if the tens digit of 10 a is 9, the sum of digits of 10( a − 1) is
    N − 1, which is also divisible by 11. Thus, S has at most 38 elements.
    Motivation: We want to focus on subsets of S of the form { 10 a, . . . , 10 a + 9 } , since the sum of digitsgoes up by 1 most of the time. If the tens digit of 10 a is anything other than 0 or 9, we see that S canat most contain the integers between 10 a − 8 and 10 a + 18, inclusive. However, we can attempt to make
    10( a − 1) + 9 have sum of digits congruent to N + 9 modulo 11, as to be able to add as many integersto the beginning as possible, which can be achieved by making 10( a − 1) + 9 end in the appropriatenumber of nines. We see that we want to take 10( a − 1) + 9 = 999999 so that the sum of digits uponadding 1 goes down by 53 ≡ 9 (mod 11), giving the example we constructed previously.