
Problem 10.3. How many natural numbers $\overline{a_{1} a_{2} \ldots a_{2 n}}$ exist such that:

(a) none of the digits $a_{i}$ is zero;

(b) the sum $a_{1} a_{2}+a_{3} a_{4}+\ldots+a_{2 n-1} a_{2 n}$ is an even number?


Solution: Denote the required number by $A_{n}$. The product $a_{2 i-1} a_{2 i}$ is even if at least one of the digits $a_{2 i-1}$ and $a_{2 i}$ is even. Therefore there are $5 \cdot 4+4 \cdot 5+4 \cdot 4=56$ choices for $a_{2 i-1}$ and $a_{2 i}$ such that $a_{2 i-1} a_{2 i}$ is even. Similarly, $a_{2 i-1} a_{2 i}$ is odd when both $a_{2 i-1}$ and $a_{2 i}$ are odd. There are $5 \cdot 5=25$ choices for $a_{2 i-1}$ and $a_{2 i}$ such that $a_{2 i-1} a_{2 i}$ is odd. The number of $\overline{a_{1} a_{2} \ldots a_{2 n}}$ such that $i$ of the items $a_{2 i-1} a_{2 i}$ are odd is $\binom{n}{i} 25^{i} 56^{n-i}$. Therefore $A_{n}=\sum_{i}\binom{n}{2 i} 25^{2 i} 56^{n-2 i}$. Let $B_{n}=\sum_{i}\binom{n}{2 i+1} 25^{2 i+1} 56^{n-2 i-1}$. Obviously

$$
\begin{gathered}
A_{n}+B_{n}=\sum_{i=0}^{n}\binom{n}{i} 25^{i} 56^{n-i}=(56+25)^{n}=81^{n} \\
A_{n}-B_{n}=\sum_{i=0}^{n}(-1)^{i}\binom{n}{i} 25^{i} 56^{n-i}=(56-25)^{n}=31^{n}
\end{gathered}
$$

Thus $2 A_{n}=81^{n}+31^{n}$ and $A_{n}=\left(81^{n}+31^{n}\right) / 2$.
