HMMT 十一月 2009 · 冲刺赛 · 第 9 题

HMMT November 2009 — Guts Round — Problem 9

[ 7 ] Daniel wrote all the positive integers from 1 to n inclusive on a piece of paper. After careful observation, he realized that the sum of all the digits that he wrote was exactly 10,000. Find n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . nd 2 ANNUAL HARVARD-MIT NOVEMBER TOURNAMENT, 7 NOVEMBER 2009 — GUTS ROUND

解析

[ 7 ] Daniel wrote all the positive integers from 1 to n inclusive on a piece of paper. After careful observation, he realized that the sum of all the digits that he wrote was exactly 10,000. Find n . x ∑ Answer: 799 Let S ( n ) denote the sum of the digits of n , and let f ( x ) = S ( n ). (We may add n =0 n = 0 because S (0) = 0.) Observe that: ( ) 9 9 9 9 ∑ ∑ ∑ ∑ f (99) = ( a + b ) = 10 b + 10 a = 900 a =0 a =0 b =0 b =0 If a is an integer between 1 and 9 inclusive, then: 100 a +99 100 a +99 ∑ ∑ S ( n ) = ( a + S ( n − 100 a )) = 100 a + f (99) = 100 a + 900 n =100 a n =100 a Summing, we get: a ∑ f (100 a + 99) = (100 a + 900) = 900( a + 1) + 50 a ( a + 1) n =0 This formula can be used to find benchmarks. However, it turns out that this formula alone will suffice, as things turn out rather nicely: 900( a + 1) + 50 a ( a + 1) = 10000 2 50 a + 950 a + 900 = 10000 2 50 a + 950 a − 9100 = 0 50( a + 26)( a − 7) = 0 a = 7 Therefore f (799) = 10000, and our answer is 799. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . nd 2 ANNUAL HARVARD-MIT NOVEMBER TOURNAMENT, 7 NOVEMBER 2009 — GUTS ROUND