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.
On
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.
On
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.
On
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$.
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.
On
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.
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.
and:
$$m+10(e_1+4)+9 - x \le 78$$
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]$.