Problem

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

Tags: modular arithmetic, combinatorics, decimal representation, counting, function, IMO Shortlist



Let $f(k)$ be the number of integers $n$ satisfying the following conditions: (i) $0\leq n < 10^k$ so $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


Attachments: