6
$\begingroup$

This is a question in the contest.

Prove that there exists two consecutive natural numbers such that sum of all digits of each number is multiple of $2017$.

My Solution: I take $a = \underbrace{9\dots 9}_{224}0\underbrace{9\dots 9}_{k}$ such that $2017$ divided $9\times 224 + 9k$ (at least, one can take $k=2017-224=1793$) and of course $a+1 = \underbrace{9\dots 9}_{224}1\underbrace{0\dots 0}_{k}$ which has sum of digits is $2017$.

My question: I don't think they are the smallest pair but I cannot find another smaller solution. Can someone give me a hint?

$\endgroup$
5
$\begingroup$

Let $\Sigma_n$ be the sum of the decimal digits of $n$. Then

$$\Sigma_{n+1}=\Sigma_{n}+1-9T_n$$ where $T_n$ is the number of trailing nines (because cascaded carries replace all trailing nines by zeroes).

The smallest solution of $9T_n-1=2017k$ is indeed $T_n=1793$ and you can't avoid all these nines.

As the sum of these digits is $1\mod 2017$, a total of $2016=9\cdot224$ is missing. You can't just preprend these $224$ nines, because more carries would result. It suffices to split the last nine to avoid that, and the best way is by moving one unit ahead.

The smalles pair is thus

$$1\underbrace{9\dots 9}_{223}8\underbrace{9\dots 9}_{1793}\to9\cdot2017$$

$$1\underbrace{9\dots 9}_{223}9\underbrace{0\dots 0}_{1793}\to1\cdot2017$$

$\endgroup$
  • 1
    $\begingroup$ Looking good, got the same, but seconds after your post...+1 $\endgroup$ – Macavity Oct 19 '17 at 8:11
  • $\begingroup$ @GAVD: you are close to optimal, but you moved nine units ahead when one is enough. $\endgroup$ – Yves Daoust Oct 19 '17 at 8:22
2
$\begingroup$

From your example, I got the following :

$$\underbrace{9\dots 9}_{223}18\underbrace{9\dots 9}_{1793}$$

$$\underbrace{9\dots 9}_{223}19\underbrace{0\dots 0}_{1793}$$

I got a smaller one in the similar way as above :

$$\underbrace{9\dots 9}_{222}297\underbrace{9\dots 9}_{1793}$$

$$\underbrace{9\dots 9}_{222}298\underbrace{0\dots 0}_{1793}$$

$\endgroup$
  • $\begingroup$ It looks better. But I wait more :) $\endgroup$ – GAVD Oct 19 '17 at 7:44
  • $\begingroup$ In your first solution, shifting the $1$ to left most lowers the numbers without affecting any conditions - so that's better. The second solution is larger anyway. $\endgroup$ – Macavity Oct 19 '17 at 8:22
  • $\begingroup$ @Macavity: I didn't notice that, thank you. "The second solution is larger anyway." If you mean "larger than the first solution", then I don't think so. $\endgroup$ – mathlove Oct 19 '17 at 8:28
  • $\begingroup$ @Macavity: No, in the second, $22\color{red}{2}+3+1793$. $\endgroup$ – mathlove Oct 19 '17 at 8:31
  • $\begingroup$ @mathlove OK. Same number of digits, and the first solution should start with $1$ in most significant. Hard to beat that with the second ;) $\endgroup$ – Macavity Oct 19 '17 at 8:31

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.