¿Cuántos números k dígitos son ambos divisibles por 3 e incluyen el dígito 3?

Question

Al principio pensé que yo podría simplemente contar cuántas (k-1) son números -dígitos divisible por 3 y se multiplica por k, que representa las diferentes ubicaciones posibles de la final 3. Sin embargo, parece que el método incluye duplicados.

Cualquier dirección, como la inclusión-exclusión o algo más inteligente sería apreciada. Me gustaría ser capaz de aplicarlo a 9 en lugar de 3, así. (Un método general para cualquier dígito d . Realmente solucionarían el problema original provocando esta pregunta)

Answer 1

Utilice principio de inclusión/exclusión:

---

Incluir el número de valores positivos con $k$ dígitos:

$$\color\red{9\cdot10^{k-1}}$$

---

Excluir el número de valores positivos con $k$ no$3$ dígitos:

$$\color\green{8\cdot9^{k-1}}$$

---

Excluir el número de valores positivos con $k$ dígitos que no son divisibles por $3$:

$$\color\orange{9\cdot10^{k-1}-9\cdot10^{k-1}/3}$$

---

Incluir el número de valores positivos con $k$ no$3$ dígitos que no son divisibles por $3$:

$$\color\purple{8\cdot9^{k-1}-8\cdot9^{k-1}/3}$$

---

Finalmente, obtenemos:

$$\color\red{9\cdot10^{k-1}}-\color\green{8\cdot9^{k-1}}-(\color\orange{9\cdot10^{k-1}-9\cdot10^{k-1}/3})+(\color\purple{8\cdot9^{k-1}-8\cdot9^{k-1}/3})$$

---

Que puede ser reducido a:

$$3\cdot10^{k-1}-24\cdot9^{k-2}$$

Answer 2

Contamos el número de secuencias de $k$ dígitos que no comienzan con $0$, no contienen $3$, suma de dígitos múltiples de $3$.

¿Cuántos hay?

Hay $8\times 9^{k-2}\times 3$ tales secuencias, esto es porque no se $8\times 9^{k-2}$ opciones para el primer $k-1$ términos, y luego, el último término tendrá su congruencia clase de pre-determinados por las otras opciones, y cada clase de congruencia ha $3$ opciones (si excluimos $3$).

Sin embargo, desea que el número de secuencias que hacer contengan $3$. Cuántas secuencias hay en total? Es decir, secuencias de longitud $k$ que no comienzan con $0$, suma de los dígitos es divisible entre $3$? Este es igual al número de múltiplos de $3$ $10^{k-1}$ $10^{k}-1$ incluido, lo que es $3\times 10^{k-1}$.

Por lo que su resultado final es $3\times10^{k-1}-8\times9^{k-2}\times 3$

Answer 3

Llegamos de los primeros principios de la generación de la función

$$f(z) = (z+z^2+A+z+z^2+1+z+z^2+1) \\ \times \prod_{q=1}^{k-1} (1+z+z^2+A+z+z^2+1+z+z^2+1).$$

Este es

$$f(z) = (Un + 2 + 3z + 3z^2) \prod_{q=1}^{k-1} (A + 3 + 3z + 3z^2).$$

Obtenemos para el que desee contar

$$\frac{1}{3} \sum_{q=0}^2 \a la izquierda. \left(f(z) - \a la izquierda. f(z)\right|_{A=0}\right) \right|_{A=1, z=\exp(2\pi i q/3)}.$$

Aquí podemos restar los valores de $A=0$ a eliminar las contribuciones de donde el dígito de tres no se produce.

El valor de $q=0$ es

$$(A + 8) \prod_{q=1}^{k-1} (A + 9).$$

Restando el valor de $A=0$ y ajuste de $A=1$ rendimientos

$$9\times 10^{k-1} - 8 \times 9^{k-1}.$$

Para $q=1$ $q=2$ tenemos

$$(A - 1) \prod_{q=1}^{k-1} A.$$ This is zero when we set $A=0$ y también al $A=1$ y por lo tanto no hace ninguna contribución.

Este rendimientos para el resultado final

$$\frac{1}{3} (9\times 10^{k-1} - 8 \times 9^{k-1}) = 3\times 10^{k-1} - 24 \times 9^{k-2}.$$