¿Cuántos números naturales de 4 dígitos hay, tales que la suma de sus dígitos no es mayor que 31?

Question

¿Cuántos números naturales de 4 cifras hay, tales que la suma de sus dígitos no es mayor que 31? ¿Cómo abordar este problema? He intentado aplicar los números de stirling, pero sin éxito.

Answer 1

Actualización:

Probablemente sea más fácil considerar un conjunto complementario.

El conjunto de números naturales tales que la suma de los dígitos menores o iguales a $4.$

Para cada número de este conjunto hay un número correspondiente en el otro conjunto tal que

$x+ y = 9999$

Y esto nos dará la cuenta de números de 4 dígitos con la suma de dígitos mayor que 31. Restamos esto de la cantidad de números de 4 dígitos.

$9000- {7\choose 3}-{6\choose 3}-{5\choose 3}-{4\choose 3}-{3\choose 3}\\ 9000-35-20-10-4-1\\ 8930$

Answer 2

¿Cuántos enteros positivos de cuatro dígitos tienen la suma de dígitos como máximo $31$ ?

Dejemos que $x_1$ , $x_2$ , $x_3$ , $x_4$ denotan, respectivamente, el dígito de los miles, el de las centenas, el de las decenas y el de las unidades. Entonces queremos contar el número de soluciones de la desigualdad $$x_1 + x_2 + x_3 + x_4 \leq 31 \tag{1}$$ con sujeción a las restricciones $0 \leq x_1 \leq 9$ , $1 \leq x_2 \leq 9$ , $1 \leq x_3 \leq 9$ , $1 \leq x_4 \leq 9$ .

Sin la restricción, hay $9$ formas de rellenar el dígito de los miles, $10$ formas de llenar el dígito de la centena, $10$ formas de rellenar la cifra de las decenas, y $10$ formas de llenar el dígito de las unidades, por lo que hay $9 \cdot 10 \cdot 10 \cdot 10 = 9000$ números enteros positivos de cuatro dígitos. De ellos, queremos restar los casos en los que la suma de dígitos es mayor que $31$ .

La restricción de que la suma de dígitos debe ser como máximo $31$ se infringe si $$x_1 + x_2 + x_3 + x_4 \geq 32 \tag{2}$$ con las mismas restricciones que las anteriores.

Para convertir esto en una desigualdad en los enteros no negativos, dejamos que $x_1' = x_1 - 1$ . Entonces $x_1'$ es un número entero no negativo. Sustituyendo $x_1' + 1$ para $x_1$ en la desigualdad 2 y simplificando se obtiene $$x_1' + x_2 + x_3 + x_4 \geq 31 \tag{3}$$ donde $x_1', x_2, x_3, x_4$ son enteros no negativos que satisfacen $x_1' \leq 8$ , $x_2, x_3, x_4 \leq 9$ .

Dejemos que $y_1 = x_1' - 8$ ; dejar que $y_2 = x_2 - 9$ ; dejar que $y_3' = x_3 - 9$ ; dejar que $y_4' = x_4 - 9$ . Entonces $y_1, y_2, y_3, y_4$ son enteros no negativos. Sustituyendo $8 - y_1$ para $x_1'$ , $9 - y_2$ para $x_2$ , $9 - y_3$ para $x_3$ y $9 - y_4$ para $x_4$ en la ecuación 3 da como resultado \begin {align*} 8 - y_1 + 9 - y_2 + 9 - y_3 + 9 - y_4 & \geq 31 \\ -y_1 - y_2 - y_3 - y_4 & \geq -4 \\ y_1 + y_2 + y_3 + y_4 & \leq 4 \tag {4} \end {align*} donde $y_1, y_2, y_3, y_4$ son enteros no negativos que satisfacen $y_1 \leq 8$ , $y_2 \leq 9$ , $y_3 \leq 9$ , $y_4 \leq 9$ .

Podemos convertir la desigualdad en una ecuación introduciendo una variable de holgura. Sea $s = 4 - (y_1 + y_2 + y_3 + y_4)$ . Entonces $s$ es un número entero no negativo. Además, $$y_1 + y_2 + y_3 + y_4 + s = 4 \tag{5}$$ Una solución particular de la ecuación 5 corresponde a la colocación de cuatro signos de suma en una fila de cuatro unos. Por ejemplo, $$1 + + 1 1 + 1 +$$ corresponde a la solución $y_1 = 1$ , $y_2 = 0$ , $y_3 = 2$ , $y_4 = 1$ , $s = 0$ ( $x_1' = 8$ , $x_2 = 9$ , $x_3 = 7$ , $x_4 = 8$ o el número $9978$ ). El número de estas soluciones es $$\binom{4 + 5 - 1}{5 - 1} = \binom{8}{4} = 70$$ ya que debemos elegir qué cuatro de las ocho posiciones necesarias para cuatro unos y cuatro signos de adición se llenarán con signos de adición.

Por lo tanto, el número de enteros positivos de cuatro dígitos con suma de dígitos como máximo $31$ es $$9000 - \binom{8}{4} = 9000 - 70 = 8930$$

Answer 3

¿Cuántos enteros positivos de cuatro dígitos tienen la suma de dígitos como máximo $31$ ?

Utilizamos el Principio de inclusión-exclusión .

Dejemos que $x_1$ , $x_2$ , $x_3$ y $x_4$ sean, respectivamente, el dígito de los miles, el de las centenas, el de las decenas y el de las unidades del número. Entonces $$x_1 + x_2 + x_3 + x_4 \leq 31 \tag{1}$$ donde $x_1, x_2, x_3, x_4$ son números enteros que satisfacen las restricciones $1 \leq x_1 \leq 9$ , $0 \leq x_2 \leq 9$ , $0 \leq x_3 \leq 9$ , $0 \leq x_4 \leq 9$ .

Para convertir el problema en uno en los enteros no negativos, dejemos $x_1' = x_1 - 1$ . Desde $x_1$ es un número entero positivo, $x_1'$ es un número entero no negativo. Sustituyendo $x_1' + 1$ para $x_1$ en la desigualdad 1 y simplificando se obtiene $$x_1' + x_2 + x_3 + x_4 \leq 30 \tag{2}$$ A continuación, convertimos la ecuación en una desigualdad introduciendo una variable de holgura. Sea $s = 30 - (x_1' + x_2 + x_3 + x_4)$ . Desde $x_1', x_2, x_3, x_4$ son enteros no negativos que satisfacen $0 \leq x_1' \leq 8$ , $0 \leq x_2 \leq 9$ , $0 \leq x_3 \leq 9$ , $0 \leq x_4 \leq x_9$ , $s$ también es un número entero no negativo. Además, $$x_1' + x_2 + x_3 + x_4 + s = 30 \tag{3}$$ La ecuación 3 es una ecuación en los enteros no negativos.

Una solución particular de la ecuación 3 corresponde a la colocación de cuatro signos de suma en una fila de treinta unos. Por ejemplo, $$1 1 1 1 1 + 1 1 1 + 1 1 1 1 1 1 1 + + 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1$$ corresponde a la solución $x_1' = 5$ , $x_2 = 3$ , $x_3 = 7$ , $x_4 = 0$ , $s = 15$ y el número entero de cuatro dígitos $6370$ con suma de dígitos $16 \leq 31$ . El número de soluciones de la ecuación 3 en los enteros no negativos es $$\binom{30 + 5 - 1}{5 - 1} = \binom{34}{4}$$ ya que debemos elegir qué cuatro de las treinta y cuatro posiciones necesarias para treinta unos y cuatro signos de adición se llenarán con signos de adición.

De ellos hay que restar los casos en los que se violan una o más restricciones. Obsérvese que es posible violar simultáneamente como máximo tres de las restricciones, ya que si $x_1' > 8$ , $x_2 > 9$ , $x_3 > 9$ y $x_4 > 9$ entonces $x_1' + x_2 + x_3 + x_4 \geq 9 + 10 + 10 + 10 = 39 > 30$ .

Se infringe una restricción : Hay dos posibilidades: $x_1' > 8$ o una de las variables $x_2, x_3, x_4 > 9$ .

Supongamos que $x_1' > 8$ . Dejemos que $x_1'' = x_1' - 9$ . Entonces $x_1''$ es un número entero no negativo. Sustituyendo $x_1'' + 8$ para $x_1'$ en la ecuación 3 y simplificando se obtiene $$x_1'' + x_2 + x_3 + x_4 + s = 21 \tag{4}$$ La ecuación 4 es una ecuación en los enteros no negativos con $$\binom{21 + 5 - 1}{5 - 1} = \binom{25}{4}$$ soluciones.

Hay tres maneras de elegir cuál de las otras variables excede $9$ . Supongamos que $x_2 > 9$ . Sea $x_2' = x_2 - 10$ . Entonces $x_2'$ es un número entero no negativo. Sustituyendo $x_2' + 8$ para $x_2$ en la ecuación 3 y simplificando se obtiene $$x_1' + x_2' + x_3 + x_4 + s = 20 \tag{5}$$ La ecuación 5 es una ecuación en los enteros no negativos con $$\binom{20 + 5 - 1}{5 - 1} = \binom{24}{4}$$ soluciones. Por lo tanto, hay $$\binom{3}{1}\binom{24}{4}$$ soluciones en las que $x_2 > 9$ , $x_3 > 9$ o $x_4 > 9$ .

Si nos limitamos a restar los casos en los que se viola una de las restricciones, habremos restado demasiado, ya que habremos restado dos veces cada caso en el que se violan dos restricciones, una por cada forma en la que podríamos haber designado una de las restricciones como la que se viola. Sólo queremos restar una vez, así que debemos volver a sumar.

Se violan dos restricciones : Consideramos los casos, dependiendo de si $x_1' > 8$ es una de las restricciones violadas.

$x_1' > 8$ y una de $x_2, x_3, x_4 > 9$ : Supongamos que $x_1' > 8$ y $x_2 > 9$ . Sea $x_1'' = x_1 - 9$ ; dejar que $x_2' = x_2 - 10$ . Entonces $x_1''$ y $x_2'$ son enteros no negativos. Sustituyendo $x_1'' + 9$ para $x_1$ y $x_2' + 10$ para $x_2$ en la ecuación 3 y simplificando se obtiene $$x_1'' + x_2' + x_3 + x_4 + s = 11 \tag{6}$$ La ecuación 6 es una ecuación en los enteros no negativos con $$\binom{11 + 5 - 1}{5 - 1} = \binom{15}{4}$$ soluciones. Por simetría, el número de soluciones en las que las restricciones $x_1' > 8$ y $x_3 > 9$ o $x_1' > 8$ y $x_3 > 9$ es igual al número de soluciones en las que $x_1 > 8$ y $x_2 > 9$ . Por lo tanto, el número de casos en los que $x_1 > 8$ y una de $x_2, x_3, x_4 > 9$ es $$\binom{3}{1}\binom{15}{4}$$

Dos de $x_2, x_3, x_4 > 9$ : Hay $\binom{3}{2}$ formas de elegir qué variables superan $9$ . Supongamos que son $x_2$ y $x_3$ . Sea $x_2' = x_2 - 10$ ; dejar que $x_3' = x_3 - 10$ . Sustituyendo $x_2' + 10$ para $x_2$ y $x_3 + 10$ para $x_3$ en la ecuación 3 y simplificando se obtiene $$x_1' + x_2' + x_3' + x_4' + s = 10 \tag{7}$$ La ecuación 7 es una ecuación en los enteros no negativos con $$\binom{10 + 5 - 1}{5 - 1} = \binom{14}{4}$$ soluciones. Por lo tanto, hay $$\binom{3}{2}\binom{14}{4}$$ soluciones en las que dos de $x_2, x_3, x_4 > 9$ .

Si restamos los casos en los que se viola una restricción y luego sumamos los casos en los que se violan dos restricciones, no habremos restado los casos en los que se violan tres restricciones. Esto se debe a que los restamos tres veces, una por cada forma en que podríamos designar una de ellas como la restricción que se viola, y los sumamos tres veces, una por cada una de las $\binom{3}{2}$ formas podríamos designar dos de ellas como las restricciones que se violan. Por lo tanto, debemos restar del total los casos en los que se violan tres restricciones.

Se violan tres restricciones : Consideramos los casos, dependiendo de si $x_1' > 9$ es una de las restricciones violadas.

$x_1' > 8$ y dos de $x_2, x_3, x_4 > 9$ : Hay $\binom{3}{2}$ formas de elegir qué dos de las variables $x_2, x_3, x_4 > 9$ . Supongamos que $x_1' > 8$ y $x_2, x_3 > 9$ . Sea $x_1'' = x_1 - 9$ , $x_2' = x_2 - 10$ , $x_3' = x_3 - 10$ . Entonces $x_1'', x_2', x_3'$ son enteros no negativos. Sustituyendo $x_1' + 9$ para $x_1$ , $x_2' + 10$ para $x_2$ y $x_3' + 10$ para $x_3$ en la ecuación 3 y simplificando se obtiene $$x_1'' + x_2' + x_3' + x_4 + s = 1 \tag{8}$$ La ecuación 8 es una ecuación en los enteros no negativos con $$\binom{1 + 5 - 1}{5 - 1} = \binom{5}{4}$$ soluciones. Por lo tanto, hay $$\binom{3}{2}\binom{5}{4}$$ soluciones en las que $x_1' > 8$ y dos de $x_2, x_3, x_4 > 9$ .

$x_2, x_3, x_4 > 9$ : Dejemos que $x_2' = x_2 - 10$ ; dejar que $x_3' = x_3 - 10$ ; dejar que $x_4' = x_4 - 10$ . Entonces $x_2', x_3', x_4'$ son enteros no negativos. Sustituyendo $x_2' + 10$ para $x_2$ , $x_3' + 10$ para $x_3$ y $x_4' + 10$ para $x_4$ en la ecuación 3 y simplificando se obtiene $$x_1' + x_2' + x_3' + x_4' + s = 0 \tag{9}$$ La ecuación 9 es una ecuación en los enteros no negativos con $$\binom{3}{3}\binom{4}{4}$$ soluciones.

Por el Principio de Inclusión-Exclusión, el número de enteros positivos de cuatro dígitos con suma de dígitos como máximo $31$ es $$\binom{34}{4} - \binom{25}{4} - \binom{3}{1}\binom{24}{4} + \binom{3}{1}\binom{15}{4} + \binom{3}{2}\binom{14}{4} - \binom{3}{2}\binom{5}{4} - \binom{3}{3}\binom{4}{4} = 8930$$

Answer 4

Uso de funciones generadoras. Número total de $4$ números de dígitos es $9000$ .

Queremos encontrar: $$[x^i](x^0+x^1+\cdots+x^9)^4, i\le 31.$$ Usando el complemento, encontramos: $$[x^i](x^0+x^1+\cdots+x^9)^4, i\ge 32$$ Consideramos el caso $i=32$ : $$[x^{32}](x^0+x^1+\cdots+x^9)^4= \\ [x^{32}]\left(\frac{1-x^{10}}{1-x}\right)^4=[x^{32}](1-x^{10})^4(1-x)^{-4}=\\ [x^{32}]\sum_{k=0}^4 {4\choose k}(-x^{10})^k\sum_{k=0}^{\infty}{-4\choose k}(-x)^k=\\ [x^{32}]\sum_{k=0}^4 {4\choose k}(-x^{10})^k\sum_{k=0}^{\infty}{3+k\choose k}x^k=\\ {4\choose 0}{35\choose 32}-{4\choose 1}{25\choose 22}+{4\choose 2}{15\choose 12}-{4\choose 3}{5\choose 2}=35.$$ Del mismo modo, para los casos $i=33,34,35,36$ : $${4\choose 0}{36\choose 33}-{4\choose 1}{26\choose 23}+{4\choose 2}{16\choose 13}-{4\choose 3}{6\choose 3}=20;\\ {4\choose 0}{37\choose 34}-{4\choose 1}{27\choose 24}+{4\choose 2}{17\choose 14}-{4\choose 3}{7\choose 4}=10;\\ {4\choose 0}{38\choose 35}-{4\choose 1}{28\choose 25}+{4\choose 2}{18\choose 15}-{4\choose 3}{8\choose 5}=4;\\ {4\choose 0}{39\choose 36}-{4\choose 1}{29\choose 26}+{4\choose 2}{19\choose 16}-{4\choose 3}{9\choose 6}=1. $$ Por lo tanto: $$9000-35-20-10-4-1=8930.$$

Answer 5

Podemos emparejar los números de cuatro cifras con suma de dígitos mayor que 31 con los que tienen suma de dígitos menor que 5 (o, equivalentemente, menor o igual que 4). Emparejamos un número con dígitos $a, b, c, d$ con el número con dígitos $w = 9-a, x = 9-b, y = 9-c, z = 9-d$ . Entonces, si $abcd$ tiene suma de dígitos $S$ entonces $wxyz$ tiene suma de dígitos $36-S$ . Por ejemplo, emparejamos $8988$ (suma de dígitos 33) con 1011 (suma de dígitos 3). Permitiré la posibilidad de que $a = 9$ y así $9 - a = 0$ .

Así que ahora buscamos el número de soluciones para $w + x + y + z \le 4$ en números enteros positivos. Esto puede resolverse mediante el método de "estrellas y barras". (Véase, por ejemplo, el Artículo de la Wikipedia sobre estrellas y barras. Introducir una nueva variable v que sea un número entero positivo, y encontrar soluciones a $v + w + x + y + z = 4$ en su lugar. Ahora podemos emparejar estas soluciones con arreglos de 4 "estrellas" y 4 "barras" - por ejemplo el arreglo |*|*||** se empareja con la suma $0 + 1 + 1 + 0 + 2$ , tomando el número de "estrellas" * entre cada par de "barras" | . Y, por supuesto, hay ${8 \choose 4} = 70$ tales disposiciones de estrellas y barras, cada una de las cuales se empareja con un número. Por ejemplo |*|*||** se empareja con $0 + 1 + 1 + 0 + 2$ Si quitamos el 0 de delante, obtenemos 1102, y lo emparejamos con el número 8879 que tiene la suma de dígitos 32.