HMMT 十一月 2023 · 冲刺赛 · 第 31 题
HMMT November 2023 — Guts Round — Problem 31
题目详情
- [17] Let s ( n ) denote the sum of the digits (in base ten) of a positive integer n . Compute the number of 4 positive integers n at most 10 that satisfy s (11 n ) = 2 s ( n ) .
解析
- [17] Let s ( n ) denote the sum of the digits (in base ten) of a positive integer n . Compute the number 4 of positive integers n at most 10 that satisfy s (11 n ) = 2 s ( n ) . Proposed by: Rishabh Das Answer: 2530 Solution 1: Note 2 s ( n ) = s (10 n ) + s ( n ) = s (11 n ), so there cannot be any carries when adding n and 10 n . This is equivalent to saying no two consecutive digits of n sum to greater than 9. 4 4 We change the problem to nonnegative integers less than 10 (as both 0 and 10 satisfy the condition) so that we simply consider 4-digit numbers, possibly with leading 0s. Letting our number be abcd , we ′ ′ ′ ′ need a + b ≤ 9, b + c ≤ 9, and c + d ≤ 9. Letting b = 9 − b and d = 9 − d , this means a ≤ b ≥ c ≤ d . ′ ′ Summing over all possible values of b and d , we want 10 X x · min( x, y ) . x,y =1 The sum over pairs ( x, y ) with x > y is 2 2 2 2 2 (1 + 2 + · · · + 10) − (1 + 2 + · · · + 10 ) 55 − 55 · 7 = = 55 · 24 . 2 2 The sum over pairs x ≤ y is 10 X 2 2 k (11 − k ) = 11 · 55 · 7 − 55 = 55 · 22 . k =1 The final answer is 55 · (24 + 22) = 55 · 46 = 2530. Solution 2: Here is another way to calculate the sum. By doing casework on ( b, c ), the sum is X (10 − b )(10 − c ) b + c ≤ 9 9 This is the coefficient of x of 2 2 X X (10 − 11 x ) n n (10 − n ) x x = 5 (1 − x ) n ≥ 0 n ≥ 0 X n + 4 2 n = (10 − 11 x ) x 4 n ≥ 0 Thus, the answer is 13 12 11 100 − 220 + 121 = 2530 4 4 4