IMO 1999 SL N6

Origin: BLR | Category: Number Theory

Problem

Prove that for every real number M there exists an infinite arithmetic progression such that: (i) each term is a positive integer and the common difference is not di- visible by 10; (ii) the sum of the digits of each term (in decimal representation) exceeds M.

Solution

Let N be the smallest integer greater than M. We take the difference of the numbers in the progression to be of the form 10m + 1, m \inN. Hence we can take an = a0 + n(10m + 1) = bsbs−1 . . . b0 where a0 is the initial term in the progression and bsbs−1 . . . b0 is the decimal representation of an. Since 2m is the smallest integer x such that 10x \equiv1 (mod 10m + 1), it follows that 10k \equiv10l (mod 10m + 1) ⇔k \equivl (mod 2m). Hence a0 \equivan = bsbs−1 . . . b0 \equiv 2m−1  i=0 ci10i (mod 10m + 1), where ci = bi + b2m+i + b4m+i + \cdot \cdot \cdot \geq0 for i = 0, 1, . . ., 2m −1 (these ci also depend on n). We note that 2m−1 i=0 ci10i is invariant modulo 10m +1 for all n and that 2m−1 i=0 ci = s j=0 bj for a given n. Hence we must choose a0 and m such that a0 is not congruent to any number of the form 2m−1 i=0 ci10i, where c0 + c1 + \cdot \cdot \cdot + c2m−1 \leqN (c0, c1, . . . , c2m−1 \geq0). The number of ways to select the nonnegative integers c0, c1, . . . , c2m−1 such that c0 + c1 + \cdot \cdot \cdot + c2m−1 \leqN is equal to the number of strictly increasing sequences 0 \leqc0 < c0 + c1 + 1 < c0 + c1 + c2 + 2 + \cdot \cdot \cdot < c0 +c1 +\cdot \cdot \cdot+c2m−1 +2m−1 \leqN +2m−1, which is equal to the number of 2m-element subsets of {0, 1, 2, . . ., N + 2m −1}, which is
N+2m N  . For sufficiently large m we have
N+2m N  < 10m, and hence in this case one can select a0 such that a0 is not congruent to 2m−1 i=0 ci10i modulo 10m+1 for any set of integers c0, c1, . . . , c2m−1 such that c0 + c1 + \cdot \cdot \cdot + c2m−1 \leqN. Thus we have found the desired arithmetic progression.