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$
0

2 Answers 2

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$
2
  • 1
    $\begingroup$ Looking good, got the same, but seconds after your post...+1 $\endgroup$
    – Macavity
    Oct 19, 2017 at 8:11
  • $\begingroup$ @GAVD: you are close to optimal, but you moved nine units ahead when one is enough. $\endgroup$
    – user65203
    Oct 19, 2017 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$
5
  • $\begingroup$ It looks better. But I wait more :) $\endgroup$
    – GAVD
    Oct 19, 2017 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, 2017 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, 2017 at 8:28
  • $\begingroup$ @Macavity: No, in the second, $22\color{red}{2}+3+1793$. $\endgroup$
    – mathlove
    Oct 19, 2017 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, 2017 at 8:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .