# The digit sums again: how far they can be equal?

As we started "must-to-ask" questions, see Seva's post we should ask one more natural question.

For integer $n\ge 0$, let $s(n)$ denote the sum of the digits in the decimal representation of $n$.

1) What is the smallest $M=M(N)$ such that for every pair $(a,b)$, $1\le a< b\le N$ exist $n$, $1\le n\le M$ with $s(na)\ne s(nb)$?

2) One person chooses a number $a\le N$. We can choose $k$ (one by one) and ask him about $s(ka)$. What is the least number of questions $Q=Q(N)$ we need to determine $a$?

3) The same problem as 2). But we must choose ours $k_1$,...,$k_Q$ at once.

• In 2,3 the answer is 1. Once it is highly unlikely that sums for any two coincide, it is very likely that all sums are different. Just use a really big number $k$. – fedja Apr 21 '12 at 1:06
• Again, I assume that we do not distinguish 1230 and 123000, of course. – fedja Apr 21 '12 at 1:07
• For 2 and 3, alternatively you can encode all the numbers you want in a single test. Let $k$ be the smallest number such that $10^k>N$ and let $9k<10^\ell$. Now you can make a number $A$ consisting of $10^\ell$ 1's separated by $k+1$ 0's, followed by $10^{2\ell}$ 2's separated by $k+1$ 0's etc up to $10^{r\ell}$ $r$'s. Computing $s(nA)$, you can read off the entire sequence $s(nj))_{1\le j\le r}$ ($s(n)$ occurring as a multiple of $10^\ell$, $s(2n)$ as a multiple of $10^{2\ell}$ etc) – Anthony Quas Apr 21 '12 at 5:10
• Yes, this is an answer. – Alexey Ustinov Apr 27 '12 at 13:58

For 1, at least for $N=10^t+1$, $M(N)$ is greater then $10^{t-1}+9$: take $a=10^{t-1}+1, b:=10^{t}+1$, then the minimal $n$ is $10^{t-1}+9$. This implies that for $\liminf \frac{M(N)}{N}\gt \frac{1}{100}$. I think that $M(N)$ is at most $N$ always. So $M(N)$ should be asymptotically linear and both $\liminf \frac{M(N)}{N}$ and $\limsup \frac{M(N)}{N}$ should be between $1/100$ and 1.