MathDB

Nice and hard "nt" problem on digital representati

Source: German TST 2004, IMO ShortList 2003, combinatorics problem 6

July 15, 2004

modular arithmeticcombinatoricsdecimal representationcountingfunctionIMO Shortlist

Problem Statement

Let

f(k)

be the number of integers

n

satisfying the following conditions:
(i)

0\leq n < 10^k

n

has exactly

k

digits (in decimal notation), with leading zeroes 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

.
Proposed by Dirk Laurie, South Africa