IMO 2003 SL C6

Origin: SAF | Category: Combinatorics

Problem

Let f(k) be the number of integers n that satisfy the following conditions: (i) 0 \leqn < 10k, so n has exactly k digits (in decimal notation), with leading zeros allowed; (ii) the digits of n can be permuted in such a way that they yield an integer divisible by 11. Prove that f(2m) = 10f(2m −1) for every positive integer m.

Solution

Denote by ak−1ak−2 . . . a0 the decimal representation of a number whose digits are ak−1, . . . , a0. We will use the following well-known fact: ak−1ak−2 . . . a0 \equivi (mod 11) ⇐⇒ k−1  l=0 (−1)lal \equivi (mod 11). Let m be a positive integer. Define A as the set of integers n (0 \leqn < 102m) whose right 2m −1 digits can be so permuted to yield an integer divisible by 11, and B as the set of integers n (0 \leqn < 102m−1) whose digits can be permuted resulting in an integer divisible by 11. Suppose that a = a2m−1 . . . a0 \inA. Then there that satisfies 2m−1  l=0 (−1)lbl \equiv0 (mod 11). (1) The 2m-tuple (b2m−1, . . . , b0) satisfies (1) if and only if the 2m-tuple (kb2m−1 + l, . . . , kb0 + l) satisfies (1), where k, l \inZ, 11 ∤k. Since a0 + 1 ̸\equiv0 (mod 11), we can choose k from the set {1, . . . , 10} such that (a0 + 1)k \equiv1 (mod 11). Thus there is a permutation of the 2m-tuple ((a2m−1+1)k−1, . . ., (a1+1)k−1, 0) satisfying (1). Interchanging odd and even positions if necessary, we may assume that this permutation keeps the 0 at the last position. Since (ai + 1)k is not divisible by 11 for any i, there is a unique bi \in{0, 1, . . ., 9} such that bi \equiv(ai + 1)k −1 (mod 11). Hence the number b2m−1 . . . b1 belongs to B. Thus for fixed a0 \in{0, 1, 2, . . ., 9}, to each a \inA such that the last digit of a is a0 we associate a unique b \inB. Conversely, having a0 \in {0, 1, 2, . . ., 9} fixed, from any number b2m−1 . . . b1 \inB we can reconstruct a2m−1 . . . a1a0 \inA. Hence |A| = 10|B|, i.e., f(2m) = 10f(2m −1).