## Spring 2017, problem 36

Show that in every sequence of $79$ consecutive positive integers, there is a positive integer whose sum of digits is divisible by $13$.

Let $n$ be a number whose ones digits is zero and whose tens digits is between 0 and 6. Then in the list of 13 numbers below, $$n,n+1,n+2,n+3,\dots,n+9,n+19,n+29,n+39$$ each has a digit sum which is one more than the last. Therefore, one the digit sums is a multiple of 13.
Now, consider the range of $79$ consective numbers $m,m+1,m+2,\dots,m+78$. At least one of the numbers in the sublist $m,m+1,\dots, m+39$ satisfies the constraints in the first sentence; the worst case is when $m\equiv 61$ (mod 100), where $m+39$ is the first number ending in either 00, 10, 20, 30, 40, 50 or 60. Calling that number $n$, so $n\le m+39$, some number in the range $n,n+1,\dots,n+39\le m+78$ has a digit sum divisible by 13, and this falls in the original list.