Let $S(n)$ be the sum of digits of $n$. Determine all the pairs $(a, b)$ of positive integers, such that the expression $S(an + b) - S(n)$ has a finite number of values, where $n$ is varying in the positive integers.
Problem
Source: Brazil MO 2018 Grades 8 and 9
Tags: number theory
kaede
17.11.2018 05:47
We can take $ v\in \mathbb{N}$ $\quad$ $\quad$ such that $\quad$ $ \max\{a,b\}< 10^{v}$.
Set $\quad$ $n=\sum ^{t}_{j=1} 10^{jv}$ $\quad$ $\quad$ for$\quad$ $ t\in \mathbb{N}$.
Then we have $\quad$ $ S( an+b) =t\cdot S( a)+S(b)$ and $ S( n) =t$.
Thus, we must have $ S( a) =1$, which implies $ a=10^{k}$ for $ k\in \mathbb{N}_{\geq 0}$.
Assume that $\quad$ $ b\geq a$.
Then we can take $ u\in \mathbb{N}$ such that $\quad$ $0\leq b-au< a=10^{k}$.
Set $\quad$ $ n=10^{m} -u$ $\quad$ for $ m\in \mathbb{N}$ with $ 10^{m} >u$ .
Then we have $ S( an+b) =1+S( b-au)$ and $S( n) =9m-S( u) +1$.
Thus, we must have $ b< a$.
On the other hand, if $ a=10^{k} \ ( k\in \mathbb{N})$ and $ b< a$, $ S( an+b) -S( n) =b$.
Answer : $\quad$ $ a=10^{k} \ ( k\in \mathbb{N})$ $\quad$ and $\quad$ $ b< a$
Ilove_mathematics
21.11.2018 03:21
If $s(a) > 1$, it’s suficiente to take $n = 100...0100...01......100...0$, where the block $100...0$ (with $q > max(log_{10}a, log_{10}b)$ zeroes) appears $p$ times. So the number $an + b$ looks like $a00...a00...0a.....a00..0b$ with $p$ $a$’s and $s(an + b) - s(n) = (ps(a) + s(b)) - p = p(s(a) - 1) + s(b)$, and as we are assuming that $s(a) > 1 => s(a) - 1 > 0 => s(an + b)$ is a linear function in $p$, so as we vary $p$, $s(an + b)$ get infinite values. Now we just need to analyze the case $s(a) = 1$, that is $a = 10^k$, for some $k$ non-negative. If $s(a) = 1 => a = 10^k$, let's separe in 2 cases: $Case 1:$ If $b >= a$, then we have $b = a_1a_2a_3...a_j =>$ make $n = 999...999(10-a_1)000...000$, with $j-k-1$ zeros, and $p$ nines $=>$ we have that $a$ has $k+1$ digits, as $b >= a$, then $b$ has at least $k+1$ digits $=> j-k-1 >= 0$, so $s(an+b) = s(1000...a_2a_3a_4...a_j) = 1+s(b)-a_1$, and $s(n) = 9.p + 10-a_1$, therefore we get $s(an+b) - s(n) = (s(b)+ 1 - a_1) - (9p + 10 - a_1) = s(b) - 9.(p-1)$, lastly, we got $s(an+b) - s(n)$ in function of p, such that, as we vary p, we get infinite values for the expression $s(an+b) - s(n)$ so $a = 10^k$ and $b >= a$ isn't solution. $Case 2:$ If $b < a$, then we have that $a.n$ has $k$ zeros, and $b < a => b$ has less than k+1 digits $=> s(an+b) = s(n) + s(b)$, thus $s(an+b)- s(n) = s(n) + s(b) - s(n) = s(b)$, and we can make $s(b)$ a constant $=>$ the expression $s(an+b) - s(n)$ has a finite number of values. Thus, $s(an+b) - s(n)$ has a finite number of values, only for $a = 10^k$, $k$ is a positive integer and $b < a$. Q.E.D.