Encuentra el número de enteros positivos $$n <9,999,999 $$ para los cuales la suma de los dígitos en n es igual a 42.
¿Alguien puede darme alguna pista sobre cómo resolver esto?
Respuestas
¿Demasiados anuncios?
DiGi
Puntos
1925
Dejemos que los dígitos sean $d_1,d_2,d_3,d_4,d_5,d_6$, y $d_7$, donde permitimos ceros a la izquierda para que cada número en el intervalo especificado sea un entero de siete dígitos. Estás buscando todas las soluciones en números no negativos para
$$d_1+d_2+d_3+d_4+d_5+d_6+d_7=42\;,$$
con la restricción de que $d_k\le 9$ para $k=1,\ldots,7$. Sin la restricción, este es un problema estándar de estrellas y barras, cuya solución es
$$\binom{42+7-1}{7-1}=\binom{48}6\;.\tag{1}$$
Tanto la fórmula que utilicé aquí como una explicación/derivación bastante decente se pueden encontrar en el enlace. Sin embargo, $(1)$ incluye soluciones no deseadas en las que uno o más de los $d_k$ excede $9$. Para eliminar estas, puedes usar un argumento de inclusión-exclusión. Esta respuesta muestra dicho argumento en cierto detalle en un problema más pequeño de este tipo.
Anthony Shaw
Puntos
858
Considera el producto $(1+x+x^2+x^3+\dots+x^9)^7$. Cada elección de un término en cada factor corresponde a la elección de un dígito en un número de $7$ dígitos. El coeficiente de $x^{42}$ corresponde al número de formas en que la suma de esos dígitos puede ser $42$.
Así, la respuesta es el coeficiente de $x^{42}$ en $$ \left(\frac{1-x^{10}}{1-x}\right)^7 =\left(\sum_{j=0}^7\binom{7}{j}(-1)^jx^{10j}\right)\left(\sum_{k=0}^\infty\binom{k+6}{k}x^k\right) $$ que está dado por el producto de Cauchy de los coeficientes de la serie de potencias anteriores: $$ \sum_{j=0}^7(-1)^j\binom{7}{j}\binom{48-10j}{42-10j}=209525 $$ donde tomamos $\binom{n}{k}=0$ cuando $k\lt0$.
Handoko
Puntos
370
Una solución a través de funciones generadoras:
Imagina un lenguaje de palabras $\newcommand\L{\mathcal{L}}\L=(a^{\{0,9\}}b)^7$, donde $a^{\{0,9\}}$ significa "cualquier cantidad de $a$'s entre $0$ y $9$". Una palabra en este lenguaje corresponde a $7$ dígitos en $0,\dots,9$. La suma de los dígitos es exactamente el número de $a$'s en la palabra. Por lo tanto, queremos calcular el número de estas palabras que contienen $42$ ocurrencias de $a$.
Sea $C(x)=\sum_{w\in\L} x^{|w|_a}$, donde $|w|_a$ es el número de ocurrencias de $a$ en la palabra $w$. Entonces, el número de palabras con $42$ letras es exactamente el coeficiente de $x^{42}$ en $C(x)$, en otras palabras, es $\frac{1}{42!}\frac{d^{42}}{dx^{42}} C(x)\Bigr|_{x=0}$.
Ahora bien, la expresión regular para $\L$ es unívoca (cada palabra se obtiene exactamente una vez), por lo tanto, para obtener $C(x)$, simplemente borramos las $b$'s y cambiamos las $a$'s por $x$'s. Obtenemos $\bigl(\sum_{i=0}^9x^i\bigr)^7=\Bigl(\frac{x^{10}-1}{x-1}\Bigr)^7$. Si usas Maple y pones
eval(diff(((x^10-1)/(x-1))^7, x$42), x=0)/factorial(42);Obtendrás la respuesta correcta 209525.
Para generalizar esto, "solamente" necesitas ser capaz de obtener una fórmula general para las derivadas o ser capaz de expresar $C(x)$ de una mejor manera.
EDIT: En realidad es posible obtener la fórmula cerrada para esto. Para nuestra serie $C(x)$ tenemos que $C(x)=\Bigl(\frac{1}{1-x}-x^{10}\frac{1}{1-x}\Bigr)^7=\sum_{i=0}^7 \binom{7}{i}(-1)^i x^{10i} \Bigl(\frac{1}{1-x}\Bigr)^7$. Sea $b_n$ el coeficiente de $x^n$ en $\Bigl(\frac{1}{1-x}\Bigr)^7$. Tenemos que $b_n=\binom{n+6}{6}$. Entonces el coeficiente de $x^{42}$ en $C(x)$ es $\binom{7}{0}b_{42}-\binom{7}{1}b_{32}+\binom{7}{2}b_{22}-\binom{7}{3}b_{12}+\binom{7}{4}b_2$. Ahora puedes calcular en cualquier calculadora (o a mano) que esto realmente equivale a $209525$.
La fórmula general para $\ell$ dígitos que suman a $n$ en la base $b$ es: $$\sum_{i=0}^{\min\{\ell,\lfloor n/b\rfloor\}} (-1)^i \binom{\ell}{i} \binom{n-ib+\ell-1}{\ell-1}.$$
totaam
Puntos
111
CodingBytes
Puntos
102
Dado que $0$ no tiene peso, podemos considerar todos los números como decimales de $7$ cifras. Se sigue que tenemos que contar las soluciones de $$\sum_{k=1}^7 d_k =42,\qquad 0\leq d_k\leq 9\quad(1\leq k\leq 7)\ .$$ Olvidando la condición $d_k\leq9$, tenemos un problema estándar de estrellas y barras, que tiene ${42+7-1\choose 7-1}={48\choose6}$ soluciones.
Entre estas soluciones hay algunas con, digamos, $d_1\geq10$. Para contar estas, contamos las soluciones no negativas de $\sum_{k=1}^7 d_k=32$ (con la idea de reemplazar en cada una de estas soluciones el $d_1$ por $d_1':=d_1+10$ después). Hay ${38\choose6}$ soluciones de este tipo.
Este número de soluciones "prohibidas" debe multiplicarse por $7$, ya que cada uno de los $d_k$ podría ser $\geq10$. Pero de esta manera contamos dos veces los casos en los que dos $d_k$ son $\geq10$, y se hace evidente que nos adentramos en un esquema de inclusión-exclusión. Se sigue que el número total $N$ que estamos buscando está dado por $$N={48\choose6}-{7\choose1}{38\choose6}+{7\choose2}{28\choose6}-{7\choose3}{18\choose6}+{7\choose4}{8\choose6}=209525\ .$$ (No es posible que más de $4$ de los $d_k$ sean $\geq10$.)
