How many consecutive positive integers are at least required, such that there is always a number in such a sequence whose sum of digits is divisible by 19?
-
$\begingroup$ Just to be clear: are you asking for the minimum $N$ such that ANY sequence of $N$ consecutive positive integers contains a number whose digit sum is divisible by 19? $\endgroup$– Rand al'ThorNov 26, 2021 at 20:26
-
$\begingroup$ Yes correct, I'm asking for the minimum. $\endgroup$– ThomasLNov 26, 2021 at 20:46
1 Answer
The minimum $N$, such that ANY sequence of $N$ consecutive positive integers contains a number whose digit sum is divisible by 19, is:
199.
Proof:
Firstly, we can easily find a lower bound on $N$:
Among all the integers from $1$ up to $198$, there is no number with digit sum divisible by 19, because to get a sum of 19 we need at least two 9s and a 1 among the digits. So $N\geq199$.
Following on from the above statement, notice that
any string of consecutive integers from $100k$ to $100k+99$ contains numbers with all possible digit sums modulo 19: where $D(\cdot)$ means digit sum, we have $$D(100k)=D(k),D(100k+1)=D(k)+1,\cdots,D(100k+9)=D(k)+9,D(100k+19)=D(k)+10,D(100k+29)=D(k)+11,\cdots,D(100k+89)=D(k)+17,D(100k+99)=D(k)+18.$$
And it is clear that
any string of 199 consecutive positive integers must contain a string from $100k$ to $100k+99$ for some $k$, whether it be the last 100, the first 100, or somewhere in between.