PUMaC 2019 · 数论（A 组） · 第 3 题

PUMaC 2019 — Number Theory (Division A) — Problem 3

Consider the first set of 38 consecutive positive integers who all have sum of their digits not divisible by 11. Find the smallest integer in this set. n ∑

解析

Consider the first set of 38 consecutive positive integers who all have sum of their digits not divisible by 11. Find the smallest integer in this set. Proposed by: Marko Medvedev Answer: 999981 Consider first the last two digits. Note that if we don’t go past a multiple of 100, then we will have a string of at least 12 consecutive sums of digits since we will have a number ending in zero such that 29 plus that number has sum of digits 11 more than that number. Note that if we go up to at least 19 mod 100 then we will have 11 consecutive sums, and if we go down to at most 80 then we will have 11 consecutive sums, so we must have the range from 100 x + 81 to 100 x + 118. Then we must have the sum of digits of 100 x + 100 must have sum 1 mod 11, so x + 1 has sum of digits 1 mod 11, and 100 x + 81 must have sum 1 mod 11 so x has sum 3 mod 11. Thus when we add 1 to x we have to increase digitsum by 9 mod 11. Note that x must end in some number of nines. If it ends in k nines, then we increase by 1 − 9 k Thus 2 k + 1 = 9 (mod 11) so k = 4 so the smallest x is 9999 and our answer is 999981. ∑ n