Competition problem — Combinatorics

Library / /60 of 100

Combinatorics Difficulty 5.0 AIME, harder Prove it China

Let $S$ be the set of all those $2007$ -place decimal integers $\overline{2a_1a_2a_3\cdots a_{2006}}$ which contain odd number of digit '9' in each sequence $a_1, a_2, a_3, \cdots, a_{2006}$ . The cardinal number of $S$ is

Solution

Define $A$ as the number of the elements in $S$ , we have
$A = \binom{2006}{1} 9^{2005} + \binom{2006}{3} 9^{2003} + \dots + \binom{2006}{2005} 9.$
On the other hand,
$(9+1)^{2006} = \sum_{k=0}^{2006} \binom{2006}{k} 9^{2006-k}$
and
$(9-1)^{2006} = \sum_{k=0}^{2006} \binom{2006}{k} (-1)^k 9^{2006-k}.$
So
$\begin{aligned} A &= \binom{2006}{1} 9^{2005} + \binom{2006}{3} 9^{2003} + \dots + \binom{2006}{2005} 9 \\ &= \frac{1}{2}(10^{2006} - 8^{2006}). \end{aligned}$

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.