Consecutive Digit Sum


Solve the following problems -

    A. Find any $158$ consecutive integers such that the sum of digits for any of the numbers is not divisible by $17$.

    B. Prove that, among any $159$ consecutive integers there will always be at least one integer, whose sum of digits is divisible by $17$.



Proof Based Problems  


  0 Upvote                    0 Downvote


Solution

Disclaimer: The solutions we've shared are just one exciting approach, and there are surely many other wonderful methods out there. We’d love to hear your alternative solutions in the community thread below, so let's keep the creativity flowing!

$a)$ The sequence is $[999999999999921,~1000000000000078]$

Sum of digits of $999999999999921$ is 1 modulo 17 and sum of digits of $999999999999999$ is 16 modulo 17. Every integer in between has sum between 1 and 16 modulo 17. So, none of these sums is divisible by 17.

Sum of digits of $1000000000000000$ is 1 modulo 17 and sum of digits of $1000000000000078$ is 16 modulo 17. Every integer in between has sum between 1 and 16 modulo 17. So, none of these sums is divisible by 17.



$b)$ In any 100 consecutive integer, one of them is divisible by 100.

So, there is an integer divisible by 100 in the series.

Let the integer be $k=\overline{...00}=\overline{X00}$.

If there are at least 79 more integers after $k$ in the set, the integers:

$\overline{X00},~\overline{X01},~\overline{X02},~\overline{X03},~\overline{X04},~\overline{X05},~\overline{X06},~\overline{X07},~\overline{X08},~\overline{X09},~\\\overline{X19},~\overline{X29},~\overline{X39},~\overline{X49},~\overline{X59},~\overline{X69},~\overline{X79}$

have different sum of digit modulo 17.

But, there are 17 integers here. So, one of them has sum of digits divisible by 17.

So, there is not 79 integers after $k$ in the set.


So, there is at least $159-1-78=80$ integers in the set before $k$.

Let the number immediately before $k$ be $\overline{...99}=\overline{Y99}$.

The integers:

$\overline{Y99},~\overline{Y98},~\overline{Y97},~\overline{Y96},~\overline{Y95},~\overline{Y94},~\overline{Y93},~\overline{Y92},~\overline{Y91},~\overline{Y90},~\\\overline{Y80},~\overline{Y70},~\overline{Y60},~\overline{Y50},~\overline{Y40},~\overline{Y30},~\overline{Y20}$

have different sum of digit modulo 17.

But, there are 17 integers here. So, one of them has sum of digits divisible by 17. Proved.

This is a proof based problem added for learning purposes and does not accept submissions.

You can view the solution by clicking on the solution tab.

Editorial



Need a hint? Checkout the editorial.

View Editorial