I'm preparing myself for math competitions. And I am trying to solve this problem from the Romanian Mathematical Regional Contest “Traian Lalescu’', $2003$:
Problem $\mathbf{7}$: How many positive integers of $n$ digits chosen from the set $\{2,3,7,9\}$ are divisible by $3$?
Solution. Let $x_n,y_n,z_n$ be the number of all positive integers of $n$ digits $2,3,7$ or $9$ which are congruent to $0,1$ and $2$ modulo $3$. We have to find $x_n$.
Consider $\varepsilon=\cos\dfrac{2\pi}3+i\sin\dfrac{2\pi}3$. It is clear that $x_n+y_n+z_n=4^n$ and
$$x_n+\varepsilon y_n+\varepsilon^2z_n=\sum_{j_1+j_2+j_3+j_4=n}\varepsilon^{2j_1+3j_2+7j_e+9j_4}=(\varepsilon^2+\varepsilon^3+\varepsilon^7+\varepsilon^9)^n\;.$$
It follows that $x_n-1+\varepsilon y_n+\varepsilon^2z_n=0$. Applying Proposition $4$ in Subsection $2.2.2$ we obtain $x_n-1=y_n=z_n=k$. Then $3k=x_n+y_n+z_n-1=4^n-1$, and we find $k=\dfrac13(4^n-1)$. Finally, $x_n=k+1=\dfrac13(4^n+2)$.
Please help me with the solution, I don't understand it well enough, especially the displayed line.
Are there any other solutions for this problem?
Best Answer
Here is an alternative approach. Let $x_n,y_n$, and $z_n$ be as in the argument given in the question; clearly $x_1=2$, and $y_1=z_1=1$. For $n\ge 1$ let $X_n,Y_n$, and $Z_n$ be the sets of $n$-digit numbers using only the digits $2,3,7$, and $9$ and congruent modulo $3$ to $0,1$, and $2$, respectively (so that $x_n=|X_n|$, $y_n=|Y_n|$, and $z_n=|Z_n|$). Finally, recall that an integer is congruent modulo $3$ to the sum of its digits.
Now let $n>1$, and let $k\in X_n\cup Y_n\cup Z_n$. Let $\ell$ be the $(n-1)$-digit number obtained by removing the last digit of $k$, and let $d$ be the last digit of $k$. If $d=3$ or $d=9$, then $k\equiv\ell\pmod3$; if $d=7$, then $k\equiv\ell+1\pmod3$; and if $d=2$, then $k\equiv\ell+2\pmod3$. Thus, $k\in X_n$ iff either $d\in\{3,9\}$ and $\ell\in X_{n-1}$, or $d=2$ and $\ell\in Y_{n-1}$, or $d=7$ and $\ell\in Z_{n-1}$. These three cases are exhaustive and mutually exclusive, so
$$x_n=|X_n|=2|X_{n-1}|+|Y_{n-1}|+|Z_{n-1}|=2x_{n-1}+y_{n-1}+z_{n-1}\;.$$
Similar reasoning shows that
$$y_n=2y_{n-1}+x_{n-1}+z_{n-1}$$
and
$$z_n=2z_{n-1}+x_{n-1}+y_{n-1}\;.$$
But clearly $x_{n-1}+y_{n-1}+z_{n-1}=4^{n-1}$, so these recurrences reduce to
$$\left\{\begin{align*} x_n&=x_{n-1}+4^{n-1}\\ y_n&=y_{n-1}+4^{n-1}\\ z_n&=z_{n-1}+4^{n-1}\;. \end{align*}\right.$$
If we set $x_0=1$, the first of these recurrences holds for $n=1$ as well as for $n>1$, and we have
$$x_n=1+\sum_{k=0}^{n-1}4^k\;.$$
Finally, this is just a geometric series, so
$$x_n=1+\frac{4^n-1}{4-1}=1+\frac13(4^n-1)=\frac13(4^n+2)\;.$$