40th IMO shortlist 1999/N6 solution

40th IMO 1999 shortlist

Problem N6

Show that for any k > 0 we can find an infinite arithmetic progression of positive integers each of which has sum of digits greater than k and where the common difference is not a multiple of 10.

Solution

The AP is A, A+d, A+2d, A+3d, ... . In outline, the idea is to take the difference d large. Then we will show that there are only a small number of possibilities for the residue mod d of numbers with small digit sum. We take A to be different from these residues. Then since every term in the arithmetic progression has the same residue A mod d, it cannot have small digit sum.

So take d = 10^m + 1, where m will be chosen later (so d is obviously not a multiple of 10). Put a_n = A + nd and assume it has digits b_sb_s-1 ... b₀. If u and v differ by a multiple of 2m, then 10^u = 10^v mod (10^m + 1) (because 10^m + 1 divides 10^2m - 1 which divides 10^u - 10^v). So take c_i = b_i + b_i+2m + b_i+4m + ... for i = 0, 1, 2, ... , 2m-1. Then a_n = c_2m-110^2m-1 + ... + c₀ mod (10^m + 1).

Now we claim that the number of 2m-tuples (c₀, c₁, ... , c_2m-1) of non-negative integers with sum ≤ k is (k+2m)Ck (the binomial coefficient (k+2m)!/(k! 2m!) ). To prove the claim, note that there are (k+2m)Ck ways or arranging k 0s and 2m 1s in a row. For each such arrangement take c_j to be the number of 1s before the jth 0 (and after the j-1th 0 if there is one).

But (k+2m)Ck < 10^m for m sufficiently large. So we can find a number A in {1, 2, ... , 10^m} which is different from all of the residues c_2m-110^2m-1 + ... + c₀ mod (10^m + 1) for tuples (c₀, ... , c_2m-1) with sum ≤ k. Now if a_n had digit sum ≤ k, then the corresponding c_i would have sum equal to this digit sum and hence ≤ k so the corresponding residue c_2m-110^2m-1 + ... + c₀ mod (10^m + 1) could not be A. But a_n = A mod (10^m + 1) and a_n = c_2m-110^2m-1 + ... + c₀ mod (10^m + 1). Contradiction. So the digit sum of a_n must exceed k.

Comment.

If multiples of 10 are allowed the problem is trivial: let A = 11 ... 1 be the number with k+1 1s. Then let d be 10^2k. Now the last k+1 digits of A + nd are always the same, so A + nd always has digit sum greater than k.

40th IMO shortlist 1999