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

Question

¿Cuántos números naturales de 4 dígitos hay, tales que la suma de sus dígitos no sea mayor que 31? ¿Cómo abordar este problema? Intenté 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 tal que la suma de los dígitos sea menor o igual a $4.$

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

$x+ y = 9999$

Y esto nos dará la cantidad de números de 4 dígitos con la suma de dígitos mayor a 31. Restamos esto del número 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 una suma de dígitos a lo sumo $31$?

Sea $x_1$, $x_2$, $x_3$, $x_4$ denotan, respectivamente, el dígito de los miles, el dígito de las centenas, el dígito de las decenas, y el dígito 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}$$ sujeto 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 llenar el dígito de los miles, $10$ formas de llenar el dígito de las centenas, $10$ formas de llenar el dígito 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$ enteros positivos de cuatro dígitos. De estos, 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 a lo sumo $31$ se viola si $$x_1 + x_2 + x_3 + x_4 \geq 32 \tag{2}$$ sujeto a las mismas restricciones que antes.

Para convertir esto en una desigualdad en los enteros no negativos, permitimos que $x_1' = x_1 - 1$. Entonces $x_1'$ es un entero no negativo. Sustituyendo $x_1' + 1$ por $x_1$ en la desigualdad 2 y simplificando obtenemos $$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$.

Sea $y_1 = x_1' - 8$; sea $y_2 = x_2 - 9$; sea $y_3' = x_3 - 9$; sea $y_4' = x_4 - 9$. Entonces $y_1, y_2, y_3, y_4$ son enteros no negativos. Sustituyendo $8 - y_1$ por $x_1'$, $9 - y_2$ por $x_2$, $9 - y_3$ por $x_3$, y $9 - y_4$ por $x_4$ en la ecuación 3 obtenemos $$\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 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 ubicació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 tales soluciones es $$\binom{4 + 5 - 1}{5 - 1} = \binom{8}{4} = 70$$ ya que debemos elegir qué cuatro de las ocho posiciones requeridas para cuatro unos y cuatro signos de suma se llenarán con signos de suma.

Por lo tanto, el número de enteros positivos de cuatro dígitos con suma de dígitos a lo sumo $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

Usando funciones generadoras. El número total de números de $4$ 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.$$ De manera similar, 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 dígitos con una suma de dígitos mayor a 31 con aquellos con una suma de dígitos menor a 5 (o, equivalentemente, menor o igual a 4). Emparejamos un número con los dígitos $a, b, c, d$ con el número con los dígitos $w = 9-a, x = 9-b, y = 9-c, z = 9-d$. Entonces, si $abcd$ tiene una suma de dígitos $S$, entonces $wxyz$ tiene una 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 por lo tanto $9 - a = 0$.

Ahora estamos buscando el número de soluciones para $w + x + y + z \le 4$ en enteros positivos. Esto se puede resolver mediante el método de "estrellas y barras". (Ver por ejemplo el artículo de Wikipedia sobre estrellas y barras. Introducimos una nueva variable v que es un entero positivo, y encontramos soluciones para $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 arreglos de estrellas y barras, cada uno de los cuales se empareja con un número. Por ejemplo, |*|*||** se empareja con $0 + 1 + 1 + 0 + 2$; eliminando el 0 al principio da como resultado 1102, y emparejamos esto con el número 8879 que tiene una suma de dígitos de 32.