Maths Olympiad Prep

Library / /2 of 19

Number theory Difficulty 5.8 AIME, harder Find the answer

Let S(n)S(n) be the sum of the digits of the positive integer nn. Find all nn such that S(n)(S(n)1)=n1S(n)(S(n)-1)=n-1.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let S(n) S(n) be the sum of the digits of the positive integer n n . We want to find all n n such that:

S(n)(S(n)1)=n1. S(n)(S(n) - 1) = n - 1.

Rearranging the equation gives:

S(n)2S(n)=n1S(n)2S(n)n+1=0. S(n)^2 - S(n) = n - 1 \quad \Rightarrow \quad S(n)^2 - S(n) - n + 1 = 0.

This can be rewritten as:

S(n)2S(n)=n1. S(n)^2 - S(n) = n - 1.

Denote S(n)=s S(n) = s . Thus, the equation becomes:

s(s1)=n1n=s(s1)+1. s(s - 1) = n - 1 \quad \Rightarrow \quad n = s(s - 1) + 1.

The task is now to find all positive integers n n such that when expressed as s(s1)+1 s(s-1) + 1 , s s is the sum of the digits of n n .

Step 1: For small values of s s , calculate n=s(s1)+1 n = s(s-1) + 1 and check if s=S(n) s = S(n) .

- s=1 s = 1 :
n=10+1=1. n = 1 \cdot 0 + 1 = 1.
Check: S(1)=1 S(1) = 1 , which matches s=1 s = 1 . So, n=1 n = 1 is a solution.

- s=2 s = 2 :
n=21+1=3. n = 2 \cdot 1 + 1 = 3.
Check: S(3)=32 S(3) = 3 \neq 2 , so n=3 n = 3 is not a solution.

- s=3 s = 3 :
n=32+1=7. n = 3 \cdot 2 + 1 = 7.
Check: S(7)=73 S(7) = 7 \neq 3 , so n=7 n = 7 is not a solution.

- s=4 s = 4 :
n=43+1=13. n = 4 \cdot 3 + 1 = 13.
Check: S(13)=1+3=4 S(13) = 1 + 3 = 4 , which matches s=4 s = 4 . So, n=13 n = 13 is a solution.

- s=7 s = 7 :
n=76+1=43. n = 7 \cdot 6 + 1 = 43.
Check: S(43)=4+3=7 S(43) = 4 + 3 = 7 , which matches s=7 s = 7 . So, n=43 n = 43 is a solution.

Step 2: Continue testing for additional values of s s :

- s=10 s = 10 :
n=109+1=91. n = 10 \cdot 9 + 1 = 91.
Check: S(91)=9+1=10 S(91) = 9 + 1 = 10 , which matches s=10 s = 10 . So, n=91 n = 91 is a solution.

- s=13 s = 13 :
n=1312+1=157. n = 13 \cdot 12 + 1 = 157.
Check: S(157)=1+5+7=13 S(157) = 1 + 5 + 7 = 13 , which matches s=13 s = 13 . So, n=157 n = 157 is a solution.

After verifying calculations and checking for errors, the final set of solutions n n such that S(n)(S(n)1)=n1 S(n)(S(n) - 1) = n - 1 is:
{1,13,43,91,157} \boxed{\{1, 13, 43, 91, 157\}}

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.