Maths Olympiad Prep

Library / /160 of 348

Number theory Difficulty 4.9 AIME Find the answer

Let s(n)s(n) denote the sum of the digits (in base ten) of a positive integer nn. Compute the number of positive integers nn at most 10410^{4} that satisfy s(11n)=2s(n)s(11 n)=2 s(n)

A number or a short expression. Spacing and $ signs are ignored.

Solution

Note 2s(n)=s(10n)+s(n)=s(11n)2 s(n)=s(10 n)+s(n)=s(11 n), so there cannot be any carries when adding nn and 10n10 n. This is equivalent to saying no two consecutive digits of nn sum to greater than 9 . We change the problem to nonnegative integers less than 10410^{4} (as both 0 and 10410^{4} satisfy the condition) so that we simply consider 4 -digit numbers, possibly with leading 0 s. Letting our number be abcda b c d, we need a+b9,b+c9a+b \leq 9, b+c \leq 9, and c+d9c+d \leq 9. Letting b=9bb^{\prime}=9-b and d=9dd^{\prime}=9-d, this means abcda \leq b^{\prime} \geq c \leq d^{\prime}. Summing over all possible values of bb^{\prime} and dd^{\prime}, we want x,y=110xmin(x,y)\sum_{x, y=1}^{10} x \cdot \min (x, y) The sum over pairs (x,y)(x, y) with x>yx>y is (1+2++10)2(12+22++102)2=5525572=5524\frac{(1+2+\cdots+10)^{2}-\left(1^{2}+2^{2}+\cdots+10^{2}\right)}{2}=\frac{55^{2}-55 \cdot 7}{2}=55 \cdot 24 The sum over pairs xyx \leq y is k=110k2(11k)=11557552=5522\sum_{k=1}^{10} k^{2}(11-k)=11 \cdot 55 \cdot 7-55^{2}=55 \cdot 22 The final answer is 55(24+22)=5546=253055 \cdot(24+22)=55 \cdot 46=2530.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.