5
$\begingroup$

Find the least positive integer $k$ with the property that given any $k$ consecutive positive integers, there is at least one whose sum of digits is divisible by $11$.

I can show for $k\leq 57$. Among any $29$ consecutive positive integers with the same hundreds' digit and higher digits, at least one has sum of digits divisible by $11$. This can be checked by casework. Since our consecutive positive integers may span two different hundreds' digits, we have $k\leq 29+28=57$.

On the other hand, among the numbers $1,2,\ldots,28$ none has sum of digits divisible by $11$, so $k\geq 29$.

$\endgroup$
  • $\begingroup$ Hint: $\overline{abcd}=a\cdot10^3+b\cdot10^2+c\cdot10^1+d$, and $10=11-1$. $\endgroup$ – Lucian Jun 27 '15 at 10:04
  • $\begingroup$ @Lucian How is this useful to solve the question? $\endgroup$ – Did Jun 28 '15 at 9:20
  • $\begingroup$ Link. $\endgroup$ – Lucian Nov 11 '15 at 13:31
4
$\begingroup$

This is what happens for the numbers in the range $[1,100]$:

  1  2  3  4  5  6  7  8  9  1
  2  3  4  5  6  7  8  9 10  2
  3  4  5  6  7  8  9 10  0  3
  4  5  6  7  8  9 10  0  1  4
  5  6  7  8  9 10  0  1  2  5
  6  7  8  9 10  0  1  2  3  6
  7  8  9 10  0  1  2  3  4  7
  8  9 10  0  1  2  3  4  5  8
  9 10  0  1  2  3  4  5  6  9
 10  0  1  2  3  4  5  6  7  1

and this what happens in the range $[101,200]$ (just a $+1$ with respect to the previous table)

  2  3  4  5  6  7  8  9 10  2
  3  4  5  6  7  8  9 10  0  3
  4  5  6  7  8  9 10  0  1  4
  5  6  7  8  9 10  0  1  2  5
  6  7  8  9 10  0  1  2  3  6
  7  8  9 10  0  1  2  3  4  7
  8  9 10  0  1  2  3  4  5  8
  9 10  0  1  2  3  4  5  6  9
 10  0  1  2  3  4  5  6  7 10
  0  1  2  3  4  5  6  7  8  2 

Then in the range $[201,300]$:

  3  4  5  6  7  8  9 10  0  3
  4  5  6  7  8  9 10  0  1  4
  5  6  7  8  9 10  0  1  2  5
  6  7  8  9 10  0  1  2  3  6
  7  8  9 10  0  1  2  3  4  7
  8  9 10  0  1  2  3  4  5  8
  9 10  0  1  2  3  4  5  6  9
 10  0  1  2  3  4  5  6  7 10
  0  1  2  3  4  5  6  7  8  0
  1  2  3  4  5  6  7  8  9  3  

Then in the range $[301,400]$:

  4  5  6  7  8  9 10  0  1  4  
  5  6  7  8  9 10  0  1  2  5         
  6  7  8  9 10  0  1  2  3  6
  7  8  9 10  0  1  2  3  4  7
  8  9 10  0  1  2  3  4  5  8
  9 10  0  1  2  3  4  5  6  9
 10  0  1  2  3  4  5  6  7 10 
  0  1  2  3  4  5  6  7  8  0  
  1  2  3  4  5  6  7  8  9  1    
  2  3  4  5  6  7  8  9 10  4

$\ldots$ and so on, till the range $[1001,1100]$.

We do not need any more table. When crossing $100n$, we always switch between two of the previous tables. So we just need to count how many consecutive non-zeroes are there, at the top and the bottom of every table, then add a little of handwork. We may check that if we cross a number of the form $100 n$, we cannot have more than $20+18$ consecutive integers with the digit sum $\not\equiv 0\pmod{11}$. Than happens, for instance, in the range $[999981,1000018]$.

Anyway:

Among $\color{red}{39}$ consecutive positive integers, there is always an integer with the digit sum $\equiv 0\pmod{11}$.

$\endgroup$
  • $\begingroup$ Why isn't that $20+28$? There are $28$ non-zero digit sums at the start of the first table. And the first table follows the fourth table in the range $[5599999999981,5600000000028]$. $\endgroup$ – TonyK Jun 28 '15 at 11:12
  • $\begingroup$ @TonyK: the issue is that $56*10^k$ has a digit sum that is a multiple of $11$. $\endgroup$ – Jack D'Aurizio Jun 28 '15 at 11:45
  • $\begingroup$ Oh yes, so it does. I will leave my comment up, in case anybody else makes the same mistake as me. $\endgroup$ – TonyK Jun 28 '15 at 11:51
  • $\begingroup$ "Anyway" is not a valid argument. The number $39$ comes out of thin air. $\endgroup$ – Christian Blatter Jun 28 '15 at 17:49
  • $\begingroup$ @ChristianBlatter: no, the number $39$ comes from analyzing, case-by-case, what happens when a particular table if followed by another one. Should I really do that case-by-case? $\endgroup$ – Jack D'Aurizio Jun 28 '15 at 18:01
3
$\begingroup$

Denote by $r(n)$ the remainder modulo $11$ of the decimal digit sum of $n$. A number $n$ is good, if $r(n)=0$.

Claim: The difference $n'-n$ between two consecutive good numbers $n$, $n'$ is at most $39$, and this bound cannot be improved.

Proof:

The numbers $n:=999\,980$ and $n':=1\,000\,019$ are consecutive good numbers with $n'-n=39$.

Now for the essential part: Denote by $p(n)\geq0$ the number of trailing nines in the decimal representation of $n$. Example: $p(4199)=2$. Then we have the recursion $$r(n+1)=r(n)+1+2p(n)\qquad({\rm mod}\ 11)\ ,\tag{1}$$ because in the transition $n\rightsquigarrow n+1$ the $p(n)$ trailing nines are replaced by zeros, and the immediately preceding digit is increased by $1$.

Assume now that $n$ is a good number. Write $$n=n_0+j$$ with $n_0$ divisible by $10$ and $0\leq j\leq 9$. Put $$n_k:=n_0+10k\qquad(k\geq1)\ .$$ If $r(n_1)\ne1$, i.e., $r(n_1)\in\{0,2,3,4,5,6,7,8,9,10\}$, then there is a good number $n'$ in the decade beginning with $n_1$, and $n'-n\leq19$.

If $r(n_1)=1$, but $r(n_2)\ne1$, then there is a good number $n'$ in the decade beginning with $n_2$, and $n'-n\leq29$.

It remains to consider the case $r(n_1)=r(n_2)=1$. The recursion $(1)$ then implies $$10+2p(n_2-1)=0\qquad({\rm mod}\ 11)\ ,$$ or $p(n_2-1)=6\ ({\rm mod}\ 11)$. In particular $p(n_2-1)\geq2$, and this enforces $p(n_3-1)=1$. Using $(1)$ again we can conclude that $r(n_3)=2$, whence $n':=n_3+9$ is good, with $n'-n\leq39$.

$\endgroup$

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.