I have found in one of the Russian highschool competitions a relatively easy puzzle & to make it more challenging replaced a certain number
by N.
The modified text runs as follows:
Prove that among N sequential positive integers there always exists a number whose s.o.d. is a multiple of 11.
a. Restore N.
b. Now prove the statement.
Let S(n) be the sum of digits of n, mod 11. e.g. S(87) = 4.
S(n) increases by 1 as n increases by 1, except when you reach multiples of 10. When n is a mutliple of 10, S(n) increases by the following (mod 11):
n is a multiple of...
10^1 > 3
10^2 > 5
10^3 > 7
10^4 > 9
10^5 > 0
10^6> 2
10^7> 4
10^8 > 6
10^9 > 8
10^10 > 10
10^11 > 1
…and then it repeats.
Any "decade" of ten consecutive numbers starting with a multiple of 10 n will contain a number whose sum of digits is a multiple of 11 unless S(n) = 1. It's easy to string together 19 numbers in a row while avoiding a multiple of 11, by starting with some number that is 1 mod 10 and has S(n) = 1. Then S(n) will go from 1  9 at which point you reach a multiple of 10 and it jumps by 3 (mod 11) back to 1. You then go from 210 at which point you reach another multiple of 10. If it’s not a multiple of 100, the next decade will include a value that has S(n) = 0. So after two decades we can only really hope to extend the sequence further by crossing a larger power of 10.
Charlie's solution works because when you cross the threshold at 1,000,000 you only add 2 to S(n), which allows you to skip directly from a number where S(n) = 10 to one where S(n) = 1. Any other power of 10 listed above would have you jump further ahead, which would lead you to reach S(n) = 0 in the next decade. Therefore crossing 1,000,000 seems like it would be the best way to preserve the longest sequences before and after, and so I suspect 39 is in fact the longest possible sequence. You can get 19 before and 19 after, plus the one “skipping” power of ten in the middle.
Edited on May 24, 2021, 6:33 pm
Edited on May 24, 2021, 6:34 pm

Posted by tomarken
on 20210524 18:33:06 