How many numbers between 0 and 1,000 have the sum of their digits equal to 15 or less?
I went about this a rather long route looking case by case and I noticed a pattern. Between 0 and 99 I found 5 cases that didn't work, between 100 and 199 10 cases that didn't work, between 200 and 299 15 cases that didn't work... etc
I got my final answer to be 725. Can someone confirm my solution?
On
Clearly, $1000$ has digit sum less than $15$.
By appending leading zeros as necessary, we can represent any nonnegative integer less than $1000$ as a three-digit string. For instance, we can represent $17$ as $017$. Notice that appending leading zeros does not change the digit sum.
Let $d_k$ be the $k$th digit. Then we want to find the number of solutions of the inequality $$d_1 + d_2 + d_3 \leq 15$$ in the nonnegative integers subject to the restrictions that $d_1, d_2, d_3 \leq 9$. We can transform the inequality into an equation with the same number of solutions. Let $$s = 15 - (d_1 + d_2 + d_3)$$ Then $s$ is a nonnegative integer and $$d_1 + d_2 + d_3 + s = 15 \tag{1}$$ Equation 1 is an equation in the nonnegative integers. A particular solution of equation 1 corresponds to the placement of three addition signs in a row of $15$ ones. For instance, $$1 1 1 1 + 1 1 1 1 1 1 + 1 1 1 + 1 1$$ corresponds to the solution $d_1 = 4$, $d_2 = 6$, $d_3 = 3$, $s = 2$, while $$+ 1 1 1 1 1 1 1 1 1 + 1 1 + 1 1 1 1$$ corresponds to the solution $d_1 = 0$, $d_2 = 9$, $d_3 = 2$, $s = 4$. The number of solutions of equation 1 is $$\binom{15 + 3}{3} = \binom{18}{3}$$ since we must select which three of the eighteen positions required for fifteen ones and three addition signs will be filled with addition signs.
However, these solutions include those in which one of the variables $d_1$, $d_2$, or $d_3$ exceeds $9$ (we do not care if $s > 9$ since it does not represent a digit). Notice that at most one variable can exceed $9$ since $2 \cdot 10 = 20 > 15$.
Suppose $d_1 > 9$. Then $d_1' = d_1 - 10$ is a nonnegative integer. Substituting $d_1' + 10$ for $d_1$ in equation 1 gives \begin{align*} d_1' + 10 + d_2 + d_3 + s & = 15\\ d_1 + d_2 + d_3 + s & = 5 \tag{2} \end{align*} Equation 2 is an equation in the nonnegative integers with $$\binom{5 + 3}{3} = \binom{8}{3}$$ solutions. By symmetry, there are an equal number of solutions of equation 1 in which $d_2 > 9$ or $d_3 > 9$. Hence, the number of solutions of equation 1 that violate the restrictions $d_1, d_2, d_3 \leq 9$ is $$\binom{3}{1}\binom{8}{3}$$ Therefore, the number of nonnegative integers less than $1000$ that have digit sum at most $15$ is $$\binom{18}{3} - \binom{3}{1}\binom{8}{3}$$ so the number of nonnegative integers that are at most $1000$ that have digit sum at most $15$ is $$\binom{18}{3} - \binom{3}{1}\binom{8}{3} + 1 = 649$$ Your proposed answer of $725$ suggests that you did not take into account the fact that the leading digit of a two-digit or three-digit number (as opposed to string) cannot be zero.
$79$ doesn't work, youve probably missed that one, because between $0-100$ there are 6 exceptions. $$99,98,97,89,88,79$$ Group them by 10s. When we go to the next hundred, (i.e. $101-200$), each group of 10s will have one extra term added(so $99,98,97$ will become $199,198,197,196$, etc) and one extra group is added ($169$).
So between $101-200$, we have: $$199,198,197,196,189,188,187,179,178,169$$
This pattern means you start with $6$ (for $0-100$) and add 4 (for $101-200$) then 5 then 6 etc, and holds up until $800$.
After $800$, the groups cross over and the pattern fails, however by sorting by $10s$ you can figure out that between 800 and 900 there are $64$ exceptions and between 900 and 1000 there are 72. This is because the pattern starts ruling out entire groups of 10s. In total the number of exceptions is $6+10+15+21+28+36+45+55+64+72=352$, or $649$ $(1001-352)$ which meet your requirement.
Here is a summary of working out exceptions for $800-900$ (the same can be applied to $900-1000$)
Exceptions: $$890-899=10$$ $$880-889=10$$ $$870-879=9$$ $$860-869=8$$ $$850-859=7$$ $$840-849=6$$ $$830-839=5$$ $$820-829=4$$ $$810-819=3$$ $$800-809=2$$ Sum of exceptions =$10+10+9+8+7+6+5+4+3+2=64$