6
$\begingroup$

Let $s(a)$ be the sum of decimal digits of a number $a$. Is it known that for any $a\ne b$ exist $n$ such that $s(na)\ne s(nb)$?

$\endgroup$
6
  • 2
    $\begingroup$ Maybe the following properties of the function $s$ could be useful; $s(a+b) \le s(a) + s(b)$ and $s(a)s(b) \le s(a)s(b)$. $\endgroup$
    – Woett
    Apr 19, 2012 at 13:25
  • 1
    $\begingroup$ And of course, the sum of digits of $a$ is divisible by $3$ (or $9$) if and only if $a$ itself is divisible by $3$ (or $9$). So $n = 1$ suffices if exactly one of $a$ and $b$ is a multiple of $3$. $\endgroup$
    – Woett
    Apr 19, 2012 at 13:30
  • 9
    $\begingroup$ Counterexample: $a=1$, $b=10$. But it's probably true (and may be reasonably easy) that the only counterexamples are those for which $b/a$ is a power of $10$. $\endgroup$ Apr 19, 2012 at 13:40
  • 5
    $\begingroup$ If the greater of $a$ and $b$ is coprime to $10$ then there exists $n$ such that $na = 10^c - 1$ for some $c$, and then clearly $s(na)>s(nb)$. [This argument would already prove the guess if the base were prime.] It may be possible to expand on this trick to deal with even numbers and multiples of $5$. $\endgroup$ Apr 19, 2012 at 14:51
  • 2
    $\begingroup$ For what it's worth, one can assume that at least one of $a,b$ is coprime to 10: if $a$ and $b$ are related as in the question, and $a$ is even, then $5a$ and $5b$ are also related as in the question, and hence so are $a/2$ and $5b$. Arguing like this one can reduce to the case where one of $a,b$ is coprime to 10 and the other is not a multiple of 10, and then one has to prove $a=b$. $\endgroup$ Apr 19, 2012 at 18:58

1 Answer 1

18
$\begingroup$

Yes, but if we replace condition $a\ne b$ to $a/b\ne 10^k$ for all integers $k$.

Lemma: $s(9n)=9s(n)$ iff decimal digits of $n$ are only 0's and 1's. Else $s(9n)<9s(n)$.

Call two numbers equivalent, if their ratio is a power of 10 (with integer exponent).

Consider numbers 1,11,111,... Two of them are congruent modulo a, hence their diffrence 11...100..0 equals $ka$ for some natural $k$. Replace pair $(a,b)$ to $(ka,kb)$ and then replace new $a$ (old $ka$) to equivalent number of the form 11...1, totally $m$ ones. Also, divide $b$ to maximal possible power of 10.

Now $s(9a)=9s(a)$, hence the same holds for $b$, hence by lemma $b$ also has only 1's and 0's in its decimal representation and the number of ones equals $m$. In particular, $b>a$ and last digit of $b$ equals 1. Now choose $N$ such that $Nb=11\dots 1$, then $Na < Nb$ and due to $s(Na)=s(Nb)$, $Na$ has a digit different from 0 and 1. Then by lemma $s(9Na)<9s(Na)$, while $s(9Nb)=9s(Nb)$. A contradiction.

I know this as an old problem by Sergey Berlov, by the way. First time I saw it in 1997 in Sochi on the event for high school students I have participated in:)

$\endgroup$
13
  • $\begingroup$ I don't quite follow the "hence $b$ also has only 1's and 0's" conclusion. What about $a=11$ and $b=2$? $\endgroup$ Apr 19, 2012 at 20:34
  • $\begingroup$ we must have $s(9b)=9s(b)$, for $b=2$ it is not so. $\endgroup$ Apr 19, 2012 at 20:39
  • 2
    $\begingroup$ You can shorten your proof by Elkies' trick: choose $N$ such that $Nb=99\dots9$, then $Nb>Na$, so $s(Nb)>s(Na)$. A contradiction. $\endgroup$
    – GH from MO
    Apr 19, 2012 at 20:40
  • $\begingroup$ Oh sorry! My stupid mistake! $\endgroup$ Apr 19, 2012 at 20:41
  • $\begingroup$ Perhaps it would be useful to emphasize that $s(n+m)\leq s(n)+s(m)$ with equality iff there is no digit carry when adding $n$ and $m$, cf. Barry's comment and Woett's very first comment. $\endgroup$
    – GH from MO
    Apr 19, 2012 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.