# Prove that in every sequence of 79 consecutive positive numbers written in decimal system there is a number whose sum of the digits is divisible by 13

Prove that in every sequence of $79$ consecutive positive numbers written in decimal notation there is a number the sum of whose digits is divisible by $13$.

I tried to take one by one sets of $79$ consecutive positive numbers. Then I tried to solve with sets,relation,function. But I am not getting any idea how to start solving the question.

• Looks like a cute problem, but surely you can provide a little more context. Where does it come from? (It looks lika a competition style problem.) Also, please don't state the actual question in the title only.
– mrf
Commented Nov 11, 2015 at 6:54
• It is a AMTI second level problem in which I got selected but no one answer Commented Nov 11, 2015 at 7:00
• $79=6\cdot13+1$ and $6=\bigg\lfloor\dfrac{13}2\bigg\rfloor.$ Commented Nov 11, 2015 at 11:48
• A related question. Commented Nov 11, 2015 at 13:33
• artofproblemsolving.com/community/… Commented Nov 12, 2015 at 9:04

For $x\in{\mathbb N}$ denote by $r(x)$ the remainder modulo $13$ of the decimal representation of $x$. If $x$ is not divisible by $10$ then $r(x)=r(x-1)+1$. If $x$ is divisible by $10$, but not by $100$, then $$r(x)=r(x-1)-9+1=r(x-1)+5\ .\tag{1}$$ If $x$ is divisible by $100$, things are more complicated; see below.

Consider a run $R:=[a\ ..\ a+78]$ of $79$ consecutive natural numbers, and assume that none of these numbers is divisible by $100$. There is a smallest number $c\leq a+9$ in this run which is divisible by $10$. Assume that $r(c)=1$. Then $(1)$ implies that the $r$-values in the interval $[c\ ..\ c+39]\subset R$ are given by $$[1\ ..\ 10],\quad[2\ ..\ 11],\quad [3\ ..\ 12],\quad[4\ ..\ 13]\tag{2}$$ and cover all remainders modulo $13$. It follows that $R$ covers all remainders modulo $13$, even if $r(c)\ne1$. Note that we would see $r(x)=0$ for an $x<c+39$ if we had not insisted in $r(c)=1$.

The run $R$ may contain at most one number $c$ divisible by $100$. Assume that $r(c-1)=12$ and $r(c)=1$. Then the $r$-values in the interval $[c\ ..\ c+39]$ are still given by $(2)$. The $r$-values in the intervall $[c-40\ ..\ c-1]$ are given by $$[0\ ..\ 9],\quad [1\ ..\ 10],\quad [2\ ..\ 11],\quad[3\ ..\ 12]\ ,$$ and cover all remainders modulo $13$. Note that we would see $r(x)=0$ for an $x>c-40$ if we had not insisted in $r(c-1)=12$.

It follows that in the worst possible case we don't see the $r$-value $0$ for all $x$ in the interval $[c-39\ ..\ c+38]$ containing $78$ integers. In order to realize this worst possible case we need $c$ divisible by $100$, $r(c)=1$, and $r(c-1)=12$. Assume that $c-1$ has $k\geq2$ trailing nines in its decimal expansion. Then the stated conditions imply $$2=r(c)-r(c-1)=-9k+1\qquad({\rm mod}\>13)\ .$$ The smallest $k\geq2$ fulfilling this is $k=10$. The number $c-1=10^{10}-1=9999999999$ already has $r(c-1)=12$, and it is obvious that $r(c)=1$ in this case.

To sum it all up: Any run of $79$ consecutive positive integers contains an $x$ with $r(x)=0$. The first run of $78$ consecutive integers containing no $x$ with $r(x)=0$ is given by $[10^{10}-39\ ..\ 10^{10}+38]$.

Look at the smallest number $a$ where the last digit is $0$. There are at most nine numbers below $a$. Now $a,a+1,...,a+9$ gives you ten distinct modulo class of modulo 13.

Now look at the second last digit of $a$, if it is less than or equal to 6 then we are good as $a,a+1,...,a+9,a+19,a+29,a+39$ gives you thirteen distinct remainders.

If the second last digit is greater or equal to $7$ then let $b=a+30$ and $b$ has last digit $0$ with second last digit at most $2$.

Now $b,b+1,...,b+9,b+19,b+29,b+39$ gives you thirteen distinct remainders.

Also $b+39=a+69$ is still in the $79$ numbers.

• I really didn't understand your answer which you are taking as "a" and which as"b" Commented Nov 11, 2015 at 7:22
• $a$ is the first number in the sequence with last digit zero. Say your sequence is $11,12,13,14,...,89$ then $a=20$. $b$ is simply $a+30=50$ Commented Nov 11, 2015 at 7:28

This is inelegant but...

For this answer I will use the notation abc to refer to the number a*100 + b*10 + c where a,b,c are positive integers and b and c are between 0 and 9. I will occasionally use a(b+3)c or some such the indicate that b+3 is a single digit between 3 and 9 (presuming that b is a single digit between 0 and 6.)

If we have 79 consecutive numbers we must have 40 from ab0 (That is a*100 + b*10 where b $\le$ 6) to a(b+3)9. (That is a*100 + (b+3)*10 + 9 where b+3 $\le$ 9).

That is obvious isn't it. If first number is between a61-a99, then the last number is more than (a+1)39 and we have all the numbers (a+1)00-(a+1)39. If the first number is between a20 and a60 then we have a60-a99. If the first number is between a00 and a19, then we have a20-a59.

No matter what, we have four consecutive "decades" within the same "century".

Lets start with the number ab0 and suppose the sum of it's digits is m. Then between ab0 to ab9 we have sums for all values m through m + 9. From a(b+3)0 through a(b+3)9 we have sums from m+3 to m+12. So between ab0 through a(b+3)9 we have sums for all the numbers m through m + 12. One of them must be divisible by 13.

• I'm not sure that your first comment is true. What if you had 110 - 188? Commented Nov 11, 2015 at 7:16
• You are absolutely right! But in that case you will have four decades so its the same. Commented Nov 11, 2015 at 7:17
• This seems to be the best approach, but the phrasing and notation of it is a bit confusing, I think. Basically one needs to confirm, that any four full consecutive decades within the same century cover all modulo classes modulo $13$. The second decade covers the same $10$ classes as the first, but shifted one up, etc. That's it. Commented Nov 11, 2015 at 12:01

Let $a_1<a_2<\cdots<a_{78}<a_{79}$ be the $79$ consecutive numbers.

Case $1$: The digit in the hundreds place is the same for all numbers, i.e., $\left\lfloor \dfrac{a_i}{100}\right\rfloor$ is the same for all numbers. Consider the smallest of the lot, which has $0$ as its last digit, say $a_k$, where $k \in \{1,2,\ldots,9\}$. Note that $k+39<79$.

• If $\text{sum}(a_k) \pmod{13} = 0$, then we are done.
• If $\text{sum}(a_k) \pmod{13} = b \in \{4,5,\ldots,12\}$, then $\text{sum}(a_{k+13-b}) \pmod{13} = 0$.
• If $\text{sum}(a_k) \pmod{13} = 3$, then $a_{k+19} \pmod{13} = 0$
• If $\text{sum}(a_k) \pmod{13} = 2$, then $a_{k+29} \pmod{13} = 0$
• If $\text{sum}(a_k) \pmod{13} = 1$, then $a_{k+39} \pmod{13} = 0$

Case $2$: There is a number $a_m$ such that $100$ divides $a_m$, i.e., if $k<m$, then $a_k$'s have same digit in hundreds place and if $k \geq m$, then $a_k$'s have same digit in hundreds place. Now repeat the same argument as above by considering either $a_0$ to $a_{m-1}$ or $a_m$ to $a_{79}$, whichever has $40$ numbers.

• I think this is not the correct answer Commented Nov 11, 2015 at 9:23
• @SarnavoSarkar, why? Commented Nov 11, 2015 at 10:36

Let $x$ be any number.

Let $d_n, d_n-1, \dots, d_1, d_0$ be the digits that make up $x$ so that $x = \sum\limits_{i=0}^{n}10^i{d_i}$

Let $m = \sum\limits_{i=2}^{n}10^i{d_i}$ so that $x = m + 10d_1 + d_0$.

If $d_1 < 6$ or $(d_1=6$ and $d_0=0)$ , then the following are distinct congruence classes modulo $13$:

Note: if $d_0 = 0$, then use $m+10(d_1), m+10(d_1)+1, \dots$ instead.

• $m+10(d_1+1)$
• $m+10(d_1+1)+1$
• $\dots$
• $m+10(d_1+1)+8$
• $m+10(d_1+1)+9$
• $m+10(d_1+2)+9$
• $m+10(d_1+3)+9$
• $m+10(d_1+4)+9$

and since $d_1 + 1 - d_0 < 10$:

$$m+10(d_1+4)+9 - x \le 48$$

If $d_1 \ge 6$, then let $e_1 = d_1+3$ and substitute $e_1$ for $d_1$ which gets us $13$ distinct congruence classes with:

Note: if $d_0 = 0$, then use $m+10(e_1), m+10(e_1)+1, \dots$ instead.

• $m+10(e_1+1)$
• $m+10(e_1+1)+1$
• $\dots$
• $m+10(e_1+1)+8$
• $m+10(e_1+1)+9$
• $m+10(e_1+2)+9$
• $m+10(e_1+3)+9$
• $m+10(e_1+4)+9$

and:

$$m+10(e_1+4)+9 - x \le 78$$