In an infinite arithmetic progression of positive integers there are two integers with the same sum of digits. Will there necessarily be one more integer in the progression with the same sum of digits? Proposed by A. Shapovalov
Problem
Source: 44th International Tournament of Towns, Senior A-Level P5, Fall 2022 & Kvant Magazine No. 11-12 2022 M2724
Tags: number theory, Tournament of Towns, sum of digits, Kvant
Anzoteh
23.02.2023 16:14
No.
Consider the sequence $3, 1011, \dots$, where the first two terms have sum of digits 3. The difference 1008 is divisible by 16, so all terms must have remainder 3 modulo 16. We show that a) among those numbers $16k+3$, the minimum sum of last 4 digits is 3, and b) there are only two such numbers up to congruence modulo 10000 (i.e. $0003$ and $1011$).
Given that such number is odd, if it's sum of last 4 digits is at most 3, then it must end with 1 or 3. In the second case the last 4 digits can only be $0003$. In the first case, since it's congruent to 3 mod 4, the tens digits must be odd, so the last two digits can only be $11$. Now that the 100s and 1000s digits have to be $\{0, 1\}$ (while cannot both be 1), we only need to consider $0011, 0111, 1011$, and only $1011$ has remainder 3 modulo 16. This justifies our claim.
Circling back to the problem, we see that all such numbers in our arithmetic progression with sum of digits = 3 must have the form $0003$ or $1011$ in the last 4 digits, and 0 elsewhere, which means there can only be two of them.
math_comb01
29.03.2023 10:55
pick $3,1011...$ then see their modular form and rule out the possibilities