Maths Olympiad Prep

Library / Cono Sur Olympiad /2 of 16

Cono Sur Olympiad

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)=n−1S(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)=n−1. S(n)(S(n) - 1) = n - 1.

Rearranging the equation gives:

S(n)2−S(n)=n−1⇒S(n)2−S(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)2−S(n)=n−1. S(n)^2 - S(n) = n - 1.

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

s(s−1)=n−1⇒n=s(s−1)+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(s−1)+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(s−1)+1 n = s(s-1) + 1 and check if s=S(n) s = S(n) .

- s=1 s = 1 :
n=1⋅0+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=2⋅1+1=3. n = 2 \cdot 1 + 1 = 3.
Check: S(3)=3≠2 S(3) = 3 \neq 2 , so n=3 n = 3 is not a solution.

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

- s=4 s = 4 :
n=4⋅3+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=7⋅6+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=10⋅9+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=13⋅12+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)=n−1 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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.