En números cuántos de los enteros entre 0 y 10.000 el número 3 aparece a la izquierda de 4

Question

¿Cuántos de los números enteros entre $0$y $10\,000$ ¿de dígitos $3$ aparece algún lugar a la izquierda de dígitos $4$? Esto incluye, por ejemplo, el % de números $34$, $374$, $4384$ y $3874$, pero no incluiría $27$, $43$, %#% de %#% o $3650$.

Así que estoy pensando que hacer $4333$ $ pero siento es demasiado baja.

Answer 1

Podemos describir los números válidos con una FSA utilizando los dígitos como alfabeto (el límite superior en el número aún no está incluido):

Aquí los números negros en las flechas indican el símbolo que se utiliza para la transición. Si no hay tal número de cada uno de los símbolos que no se usa con otra transición es válida. Los números rojos indican el número de símbolos que ese resultado en el estado de destino.

Los estados

Una: No 3 encontrado todavía (estado inicial)

B: 3 encontrado pero no 4 se encuentra a la derecha de la primera 3.

C: 4 se encuentra a la derecha de un 3 (estado final)

Podemos representar esto como un gráfico con la siguiente matriz de adyacencia (ponderado con el número de símbolos que se pueden utilizar para cada transición):

$$A=\begin{bmatrix}9&1&0\\0&9&1\\0&0&10\\\end{bmatrix}$$

Note that any path in this graph starting at vertex 1 corresponds to a number and every path also ending at vertex 3 is one of the numbers we want to count.

We only need to consider numbers 0, ..., 9999 since 10000 obviously doesn't fit the pattern. Therefore we only need to consider words with exactly 4 symbols ($\rightarrow$ path of length 4 in the graph).

Since we've chosen the edge weights of the graph appropriately the number to calculate can be directly read from last entry in the first row of the matrix

$$A^4=\begin{bmatrix}6561&2916&523\\0&6561&3439\\0&0&10000\\\end{bmatrix}$$

Answer 2

Respuesta revisada

Marca el primer $3$ y el primer $4$después de $3$, son sólo los casos de $6$:

$$\begin{array}{} 3&4&\bullet&\bullet&\implies& 10\cdot10 = 100\\ 3&\bullet&4&\bullet&\implies& 9\cdot 10 = 90\\ 3&\bullet&\bullet&4&\implies& 9\cdot9 =81\\ \bullet&3&4&\bullet&\implies& 9\cdot10 = 90\\ \bullet&3&\bullet&4&\implies& 9\cdot 9 = 81\\ \bullet&\bullet&3&4&\implies& 9\cdot9 = 81 \end{matriz} $$

Sumando, $523$.

Nota: El primer $4$ después de que se ha marcado el primer $3$, pero esto no excluye un $4$ antes de los primeros $3$.

Answer 3

Llamar a un número entero bien. La almohadilla con la inicial $0$'s si es necesario hacer una $4$-cadena de dígitos de $0000$$9999$.

Las fáciles son las que comienzan con $3$. Cualquier cadena es buena si la $3$-cadena de dígitos después de la inicial $3$ contiene un $4$. Hay $10^3$ $3$-dígito de las cadenas, de los cuales, $9^3$ no $4$, dando $271$, con al menos un $4$.

Ahora contamos con el "otro" buena cadenas. Hay $9$ veces hay buenas cadenas que comienzan con $0$, que es el mismo que el número de $3$dígitos buena cadenas.

Cuántos buenos $3$dígitos cadenas hay? Son los que comienzan con $3$. El resto de los $2$-cadena de dígitos debe contener una $4$. Hay $19$ de estos.

Luego están los que empiezan con algo más. ¿Cuántas? $9$ veces tantas como hay buen $4$-cadenas de dígitos que comienzan con $00$. No sólo es $1$ de estos.

Tenemos un total de $271+9(19+(9)(1))$.

Comentario: La misma idea se encargará del recuento de decir $000000$$999999$.

Answer 4

Deje $a_n$ denotar el número de cadenas de $n$ dígitos que contienen al menos un $3$ en algún lugar a la izquierda de al menos uno de los $4$. Se desea calcular el $a_4$.

Si $b = 0, 1, 2, 4, 5, \dots 9$, hay exactamente $a_{n-1}$ cadenas de este tipo, cuyo primer dígito es $b$. El número de cadenas de este tipo, cuyo primer dígito es $3$ es el mismo que el número de $(n-1)$dígitos cadenas que contengan al menos uno de los $4$ o $10^{n-1} - 9^{n-1}$.

Por lo tanto, $a_n$ se puede calcular mediante la relación de recurrencia $$a_n = 9a_{n-1} + 10^{n-1} - 9^{n-1}, \quad a_1 = 0.$$

Tenemos $a_2 = 1$, $a_3 = 28$, $a_4 = 523$.

O: podemos resolver esto lineal de la recurrencia de la relación para encontrar $$a_n = 10^n - (n+9)9^{n-1}.$$ A continuación, $a_4 = 10^4 - 13 \times 9^3 = 523.$

Answer 5

Aquí está mi respuesta no matemáticas: 523. Me pregunto si dividir la respuesta en 6 casos rinde duplicados. es decir, el mismo número podía contarse en más de un caso.

SYS@dbtstmra AS SYSDBA> SELECT COUNT(*) FROM ( SELECT LPAD( rownum, 4, '0') mynum FROM dba_tab_columns WHERE rownum < 10000 ) WHERE mynum LIKE '%3%4%';

  COUNT(*)
----------
       523

1 row selected.

Elapsed: 00:00:00.25