Michael's huge numbers

I apologise for the length of this solution, but I simply haven't found any elegant shortcut.

The stars and bars technique and the inclusion-exclusion principle are keys to my procedure. We first find a general solution, and then subtract all the solutions containing digits $_{ \geq 10}$ and all the solutions where the first digit is $0$ .

We have $x_{1} +x_{2} + x_{3} + x_{4} + x_{5} \geq 23$ .

The maximum possible sum is $45$ when all the digits are $9$ .

Instead of finding all the solutions between $23$ and $45$ separately, it is useful to notice that the inequality

$x_{1} +x_{2} + x_{3} + x_{4} + x_{5} \leq k$ ,

where $k$ is any integer, may be transformed to an equation by introducing a dummy-variable $x_{6}$ , which is not subjected to any restrictions:

$x_{1} +x_{2} + x_{3} + x_{4} + x_{5} + x_{6} = k$ .

(The pattern in a Pascal triangle will confirm this result).

To find the number of solutions to the original problem, the idea is then to find the number of solutions to $x_{1} +x_{2} + x_{3} + x_{4} + x_{5} \leq 45$ and subtract the number of solutions to $x_{1} +x_{2} + x_{3} + x_{4} + x_{5} \leq 22$ .

This is equivalent to finding the number of solutions to $x_{1} +x_{2} + x_{3} + x_{4} + x_{5} + x_{6}=45$ and subtracting the number of solutions to $x_{1} +x_{2} + x_{3} + x_{4} + x_{5} + x_{6}=22$ .

The solution has two main parts, A) and B).

---

A) Let us first find the number of solutions adding up to $45$ .

Without restrictions on the values of the digits, the solution is

${50 \choose 5}$ .

From this number we must subtract all digits $_{ \geq 10}$ , and all solutions containing the first digit as $0$ .

---

1) Subtracting the digits $_{ \geq 10}$ :

In order not to count any of our cases more than once, we use the inclusion-exclusion principle, i.e.:

general solution $-$ $\bigg ($ number of single digits $_{ \geq 10}$ $)$ $-$ number of double digits $_{ \geq 10}$ $+$ number of triple digits $_{ \geq 10}$ $-$ ... $+$ ... $\bigg )$ .

Choosing first one digit $x_{i} \geq 10$ , the equation is now transformed into

$x_{1} +x_{2} + x_{3} + x_{4} + x_{5} + x_{6} = 35$

which has ${ 40 \choose 5}$ solutions.

Since there are ${ 5 \choose 1}$ ways of choosing one digit, we have ${ 5 \choose 1} { 40 \choose 5}$ ways of subtracting all the $10$ 's.

However, we have now subtracted too many, for there are cases were two digits are higher than ten at the same time, and they should be counted only once. With two digits higher than $10$ , the equation is transformed to

$x_{1} +x_{2} + x_{3} + x_{4} + x_{5} + x_{6} = 25$

which has the solution ${30 \choose 5}$ .

There are ${5 \choose 2}$ ways of choosing two digits at the time, and thus we have ${ 5 \choose 2} { 30 \choose 5}$ to subtract from the first case.

Having now removed too many cases, we must add the triple cases, and then subtract quadruple cases, etc.

Continuing like this until it is no longer possible to reduce the equation further by $10$ , we find that the total number of digits $_{ \geq 10}$ to be subtracted from from the general solution is:

${5 \choose 1}{40 \choose 5} - {5 \choose 2}{30 \choose 5} + {5 \choose 3}{20 \choose 5} - {5 \choose 4}{10 \choose 5} = 2018760$ .

---

2) We can now go on to subtract also the solutions with first digit $0$ :

If we set $x_{1}=0$ , the equation transforms to

$x_{2} + x_{3} + x_{4} + x_{5} + x_{6} = 45$ .

Using the same procedure as for the previous case, but now with one less variable, we find the general solution and subtract the cases where digits >=10. This produces:

${49 \choose 4} - \bigg ( {4 \choose 1}{39 \choose 4} - {4 \choose 2}{29 \choose 4} + {4 \choose 3}{19 \choose 4} - {4 \choose 4}{9 \choose 4} \bigg ) = 10 000$ .

The number of solutions to $x_{1} +x_{2} + x_{3} + x_{4} + x_{5} + x_{6} = 45$ is then ${50 \choose 5} - 2018760 - 10000 = 90000$ .

---

B) Following the exact same procedure for the case $x_{1} +x_{2} + x_{3} + x_{4} + x_{5} + x_{6} = 22$ , the number of solutions is now found to be:

${27 \choose 5} - \bigg ( {5 \choose 1}{17 \choose 5} - {5 \choose 2}{7 \choose 5} \bigg ) - \bigg ( {26 \choose 4} -\bigg ( {4 \choose 1}{16 \choose 4} - {4 \choose 2}{6 \choose 4} \bigg ) = 42 240$ .

---

By subtracting the results B from A , we find the total number of solutions to $x_{1} +x_{2} + x_{3} + x_{4} + x_{5} \geq 23$ to be $90000-42240 = 47760$ .

The last three digits are $\boxed {760}$

Quick and Dirty solution:

The generating function for the $5$ digit numbers is $(x+x^2+\cdots+x^9)(1+x+\cdots+x^9)^4$ . We multiply this out, preferably with a calculator like Wolfram Alpha, then sum the coefficients of $x^{23}\rightarrow x^{45}$ and get $47760$ . The last three digits of this is $\boxed{760}$ .