¿Cuántos enteros positivos de n cifras elegidos del conjunto {2,3,7,9} son divisibles por 3?

Question

Me estoy preparando para las oposiciones de matemáticas. Y estoy intentando resolver este problema del Concurso Regional de Matemáticas de Rumanía "Traian Lalescu'', $2003$ :

Problema $\mathbf{7}$ : ¿Cuántos enteros positivos de $n$ dígitos elegidos del conjunto $\{2,3,7,9\}$ son divisibles por $3$ ?

Solución. Dejemos que $x_n,y_n,z_n$ sea el número de todos los enteros positivos de $n$ dígitos $2,3,7$ o $9$ que son congruentes con $0,1$ y $2$ modulo $3$ . Tenemos que encontrar $x_n$ .

Considere $\varepsilon=\cos\dfrac{2\pi}3+i\sin\dfrac{2\pi}3$ . Está claro que $x_n+y_n+z_n=4^n$ y

$$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\;.$$

De ello se desprende que $x_n-1+\varepsilon y_n+\varepsilon^2z_n=0$ . Aplicando la proposición $4$ en la subsección $2.2.2$ obtenemos $x_n-1=y_n=z_n=k$ . Entonces $3k=x_n+y_n+z_n-1=4^n-1$ y encontramos $k=\dfrac13(4^n-1)$ . Finalmente, $x_n=k+1=\dfrac13(4^n+2)$ .

Por favor, ayúdame con la solución, no lo entiendo bien, sobre todo la línea mostrada.

¿Hay alguna otra solución para este problema?

Answer 1

He aquí un enfoque alternativo. Dejemos que $x_n,y_n$ y $z_n$ ser como en el argumento dado en la pregunta; claramente $x_1=2$ y $y_1=z_1=1$ . Para $n\ge 1$ dejar $X_n,Y_n$ y $Z_n$ sean los conjuntos de $n$ -números de dígitos utilizando sólo los dígitos $2,3,7$ y $9$ y congruente módulo $3$ a $0,1$ y $2$ respectivamente (para que $x_n=|X_n|$ , $y_n=|Y_n|$ y $z_n=|Z_n|$ ). Por último, recordemos que un número entero es congruente módulo $3$ a la suma de sus dígitos.

Ahora dejemos que $n>1$ y que $k\in X_n\cup Y_n\cup Z_n$ . Sea $\ell$ sea el $(n-1)$ -número de dígitos que se obtiene eliminando el último dígito de $k$ y que $d$ sea el último dígito de $k$ . Si $d=3$ o $d=9$ entonces $k\equiv\ell\pmod3$ ; si $d=7$ entonces $k\equiv\ell+1\pmod3$ y si $d=2$ entonces $k\equiv\ell+2\pmod3$ . Así, $k\in X_n$ si $d\in\{3,9\}$ y $\ell\in X_{n-1}$ o $d=2$ y $\ell\in Y_{n-1}$ o $d=7$ y $\ell\in Z_{n-1}$ . Estos tres casos son exhaustivos y se excluyen mutuamente, por lo que

$$x_n=|X_n|=2|X_{n-1}|+|Y_{n-1}|+|Z_{n-1}|=2x_{n-1}+y_{n-1}+z_{n-1}\;.$$

Un razonamiento similar muestra que

$$y_n=2y_{n-1}+x_{n-1}+z_{n-1}$$

y

$$z_n=2z_{n-1}+x_{n-1}+y_{n-1}\;.$$

Pero claramente $x_{n-1}+y_{n-1}+z_{n-1}=4^{n-1}$ por lo que estas recurrencias se reducen a

$$\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.$$

Si ponemos $x_0=1$ la primera de estas recurrencias es válida para $n=1$ así como para $n>1$ y tenemos

$$x_n=1+\sum_{k=0}^{n-1}4^k\;.$$

Si esto no está claro de inmediato, tenga en cuenta que

$$\begin{align*} x_n&=4^{n-1}+x_{n-1}\\ &=4^{n-1}+4^{n-2}+x_{n-2}\\ &\;\vdots\\ &=4^{n-1}+4^{n-2}+\ldots+4^0+x_0\\ &=1+\sum_{k=0}^{n-1}4^k\;, \end{align*}$$

y la fórmula se puede demostrar rigurosamente por inducción en $n$ .

Finalmente, esto es sólo una serie geométrica, así que

$$x_n=1+\frac{4^n-1}{4-1}=1+\frac13(4^n-1)=\frac13(4^n+2)\;.$$