We call a positive integer $N$ contagious if there are $1000$ consecutive non-negative integers such that the sum of all their digits is $N$. Find all contagious positive integers.
Problem
Source: 2020 MEMO I-2
Tags: number theory, memo, MEMO 2020
Tintarn
30.08.2020 16:58
We claim that the set of contagious integers is exactly the set $\{13500,13501,\dots\}$ of positive integers not smaller than $13500$.
First of all, it is clear that every contagious integer is at least $13500$: Among the last three digits of $1000$ consecutive integers, every combination appears exactly once, accounting for a digital sum of
\[1000 \cdot 3 \cdot 4.5=13500.\]Now let us prove that each such number appears as a contagious number.
To this end, let $f(n)$ be the sum of the sums of digits of $\{n,n+1,\dots,n+999\}$. So $f(0)=13500$.
Moreover, it is clear that $f(n+1)-f(n)=S(n+1000)-S(n) \le 1$ and that $f$ takes arbitrarily large values (by just considering $n=999\dots 99$).
Now these two conditions clearly already easily imply that $f$ takes all values not smaller than $13500$:
For let $N$ be any such number. Let $n$ be the smallest solution of $f(n) \ge N$. Then $f(n-1)<N$ and hence $f(n)=N$ and $N$ is contagious.
Mathematicsislovely
16.09.2020 20:16
We claim that,all integer greater than equal to $13500$ are contagious,whereas no integer less than 13500 are contagious. Claim :No integer less than $13500$ are contagious. proof.Working with mod$(1000)$, we get that last 3 digit of $1000$ consecutive integer must be $000,001,002,\dots,999$ in some order. So the sum of all digits of $1000$ consecutive integer will be at least $300(0+1+2+\dots 9)=13500$.The multiplication by 300 is because of the arrival of each digit 300 times in $000,001,002,\dots,999$.$\blacksquare$ Claim:Any integer greater than 13500 is contagious. proof.For $N=13500$,it is contagious by the previous example. Take $N>13500$.Let $N-13500=q\times 1000+r$ where $0\le r \le999$.To show $N$ contagious, Write $S=\underbrace{111\dots 1}_\text{q times}\times 10^{2020}+r$.Then for $\{S,S+1,S+2\dots S+999\}$ has sum of all digit equal to $N$.$\blacksquare$
Toll
15.01.2024 17:47
let $d(i)$ denote the sum of digits of $i$ written in base $10$. for example, $d(1)=1, d(10)=1, d(99)=18)$ let $C_k=\sum_{n=k}^{k+999} d(n)$. Notice $C_0$. I initially was too lazy to calculate this, but noticed I was just stupid, you can do it pretty quickly, it's just $300*45$, or $13500$ Now it's pretty clear that this is the minimal value (look$\mod 1000$) Not notice how $C_1$ is just $C_0$, but we replace $d(0)$ with $d(1000)$, so increase the total sum by $1$. Notice more generally that if $k<1000$, if we take the step from $C_k$ to $C_{k+1}$, we are just replacing $d(k)$ by $d(1000+k$, which is just $d(k)+1$. In conclusion, all values $13500 \leq i < 14500$ can be reached. We can now finish with the following lemma: $\textit{lemma}$ if the value $N$ can be reached, then the value $N+1000$ can be reached $\textit{proof}$ this is quite easy to see. Assume $N$ can be reached by some $C_k$, then just take $m > log_{10}(k)$, and look at $d = k+10^m$, afterwards, notice $C_d$, this number is just all the numbers that we used for $C_k$, with an additional $1$ before, totaling an additional value of $1000$. By this, our solution is $\boxed{N=13500, 13501, \dots}$