Maths Olympiad Prep

Library / /154 of 520

Number theory Difficulty 6.6 National olympiad Find the answer

Find all natural numbers n n for which there exists two natural numbers a,b a,b such that
n=S(a)=S(b)=S(a+b), n=S(a)=S(b)=S(a+b) ,
where S(k) S(k) denotes the sum of the digits of k k in base 10, 10, for any natural number k. k.

[i]Vasile Zidaru[/i] and [i]Mircea Lascu[/i]

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

Solution

1. Claim: The answer is all integers n n of the form n=9k \boxed{n=9k} for some positive integer k k .

2. Proof: First, we show that n n must be divisible by 9 9 in order for the property to hold.

- Observe that for any positive integer k k , we have S(k)k(mod9) S(k) \equiv k \pmod{9} . This is because the sum of the digits of k k in base 10 is congruent to k k modulo 9.

- Given n=S(a)=S(b)=S(a+b) n = S(a) = S(b) = S(a+b) , this implies:
aba+b(mod9) a \equiv b \equiv a+b \pmod{9}
- From aa+b(mod9) a \equiv a+b \pmod{9} , we get:
a2a(mod9)    a0(mod9) a \equiv 2a \pmod{9} \implies a \equiv 0 \pmod{9}
- This implies that a a is divisible by 9, and hence S(a) S(a) is also divisible by 9. Therefore, n n must be divisible by 9.

3. Existence: Next, we show that if n=9k n = 9k for some positive integer k k , then a a and b b exist.

- Consider a=b=909090909090 a = b = \underbrace{909090\cdots909090} , where the number has exactly k k copies of 90 90 .

- This makes a+b=1818181818180 a + b = 181818\cdots1818180 , where a+b a + b has exactly k k copies of 18 18 . This gives us:
S(a)=S(b)=S(909090909090)=(9+0)k=9k S(a) = S(b) = S(909090\cdots909090) = (9+0) \cdot k = 9k
and
S(a+b)=S(1818181818180)=(1+8)k+0=9k S(a+b) = S(181818\cdots1818180) = (1+8) \cdot k + 0 = 9k
- Hence, n=S(a)=S(b)=S(a+b) n = S(a) = S(b) = S(a+b) .

Therefore, the solution is all integers n n of the form 9k 9k for some positive integer k k .

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.