Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)$?

share|improve this question
2  
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)$. –  Woett Apr 19 '12 at 13:25
1  
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$. –  Woett Apr 19 '12 at 13:30
9  
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$. –  Noam D. Elkies Apr 19 '12 at 13:40
5  
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$. –  Noam D. Elkies Apr 19 '12 at 14:51
2  
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$. –  Kevin Buzzard Apr 19 '12 at 18:58

1 Answer 1

up vote 17 down vote accepted

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:)

share|improve this answer
    
I don't quite follow the "hence $b$ also has only 1's and 0's" conclusion. What about $a=11$ and $b=2$? –  Barry Cipra Apr 19 '12 at 20:34
    
we must have $s(9b)=9s(b)$, for $b=2$ it is not so. –  Fedor Petrov Apr 19 '12 at 20:39
2  
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. –  GH from MO Apr 19 '12 at 20:40
    
Oh sorry! My stupid mistake! –  Barry Cipra Apr 19 '12 at 20:41
    
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. –  GH from MO Apr 19 '12 at 20:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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