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.

  • 1
    $\begingroup$ 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$. $\endgroup$ – fedja Apr 21 '12 at 1:06
  • 1
    $\begingroup$ Again, I assume that we do not distinguish 1230 and 123000, of course. $\endgroup$ – fedja Apr 21 '12 at 1:07
  • 3
    $\begingroup$ 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) $\endgroup$ – Anthony Quas Apr 21 '12 at 5:10
  • $\begingroup$ Yes, this is an answer. $\endgroup$ – 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.

Update. A followup question.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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