HMMT 十一月 2011 · 冲刺赛 · 第 30 题
HMMT November 2011 — Guts Round — Problem 30
题目详情
- [ 14 ] Let S be a set of consecutive positive integers such that for any integer n in S , the sum of the digits of n is not a multiple of 11. Determine the largest possible number of elements of S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . TH 4 ANNUAL HARVARD-MIT NOVEMBER TOURNAMENT, 12 NOVEMBER 2011 — GUTS ROUND Round 11
解析
- [ 14 ] Let S be a set of consecutive positive integers such that for any integer n in S , the sum of the digits 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 integer in 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 which has the same property. Note that this implies that there are consecutive integers a − 1 , a, a + 1 for which 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, the sums of digits of 10 a + 1 , 10 a + 2 , . . . , 10 a + 9 are N + 1 , N + 2 , . . . , N + 9, respectively, and it follows that 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 digits goes 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 can at 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 integers to the beginning as possible, which can be achieved by making 10( a − 1) + 9 end in the appropriate number of nines. We see that we want to take 10( a − 1) + 9 = 999999 so that the sum of digits upon adding 1 goes down by 53 ≡ 9 (mod 11), giving the example we constructed previously.