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.$
Problem
Source: BdMO 2022 Secondary P8
Tags: number theory
12.04.2022 07:42
A) $10^{15}-79, 10^{15}-78,\dots, 10^{15}+78$
12.04.2022 07:57
For B), there must be numbers in the sequence with last two digits $\{00,01,\dots, 79\}$ or $\{20,21,\dots,99\}$ such that each digits before the last two are all same. Nice problem, I like it.
07.02.2023 06:22
Quidditch wrote: A) $10^{15}-79, 10^{15}-78,\dots, 10^{15}+78$ Please explain the answer clearly.
07.02.2023 06:22
Quidditch wrote: A) $10^{15}-79, 10^{15}-78,\dots, 10^{15}+78$ Please explain the process clearly.
22.12.2023 22:30
Part A is very intuitive, Here is an Explanation I found. $\color{green} \boxed{\textbf{SOLUTION Part A}}$ $\color{magenta} \textbf{Explanation :}$ Here We need $158$ consecutive numbers. Starting with it seems $100 \to 178$ all satisfies. It tells to take $(21 \to 178)$ but problems come in $89,98$ Now it seems to take $1078$ which gives $921 \to 1078$ But here problem is $...,952,961,970...$ $$\textbf{The main thing is we have no problem for the part upper $10^{k} -1$}$$ We only worry about the part $10^{k} - j$ Now notice if the numbers below $10^k$ are of the form $99...921 \to 99....999$ Consider last two digit as they varies from $21 \to 99$ So their digital sum goes from $3 \to 18$ So we need some $i$ such that none of $9i+3,9i+4,...9i+18$ is divisible by $17,$ This part is easy, If $9i \equiv 0 \pmod {17}$ then $17|9i+17$ If $9i \equiv 1 \pmod {17}$ then $17|9i+16$ . . . If $9i \equiv 15 \pmod {17}$ then we need $9i+2$ But it's not in the list! So we need some $i$ such that $9i+2 \equiv 15 \pmod {17}$ And it's easy to find $9×13 \equiv 15 \pmod {17} \implies i=13$ So, there must be $13, 9's$ is $99...921$ and a total of $15$ digits. Hence, $\color{blue} \textbf{Construction :}$ $$S=(10^{15} - 79 \to 10^{15} + 78), |S|=158 \blacksquare$$ $\color{green} \boxed {\textbf{SOLUTION Part B}}$ Here I found When we have $159$ numbers then we have $(99...920 \to 99...999)$ Which tells to find $j$ such that none of $(9j+2,9j+3,...9j+18) \equiv (9j+k, 0\le k \le 16)$ is divisible by $17$ which is not possible as no such $j$ exists $\blacksquare$