# All 3 digit numbers the sum of whose digits is not greater than 16

My working: Let the digits of the numbers be $x,y,z$ where
\begin{align}1\leq x&\leq 9\\0\leq y,z&\leq 9\\x+y+z &\leq 16 \end{align} I tried to solve it by making different cases here and using counting but it got really complicated and i couldnt get very far.
So how do i solve such questions?

• Where does 16 come from? – GoodDeeds Apr 5 '16 at 13:51
• so sorry i made a typo the sum is not greater than 16 not 3. – Dèsjardins Apr 5 '16 at 13:58
• You could look up any of the many posts talking about stars and bars on this site, and also the comibinatorics version in Wikipedia. – Ross Millikan Apr 5 '16 at 14:02
• Ohh okay i shall check those out. Thanks :) – Dèsjardins Apr 5 '16 at 14:07

Let $h$ denote the hundreds digit, $t$ denote the tens digit, and $u$ denote the units digit. Since the digit sum is at most $16$, $$h + t + u \leq 16 \tag{1}$$ where $1 \leq h \leq 9$, $0 \leq t \leq 9$, and $0 \leq u \leq 9$.

Let $h' = h - 1$. Then $h'$ is a non-negative integer satisfying the inequalities $0 \leq h' \leq 8$. Substituting $h' + 1$ for $h$ in inequality 1 yields \begin{align*} h' + 1 + t + u \leq 16\\ h' + t + u \leq 15 \tag{2} \end{align*} Inequality 2 is an inequality in the non-negative integers.

If we let $s = 15 - (h' + t + u)$, then we obtain the equation $$h' + t + u + s = 15 \tag{3}$$ which is an equation in the non-negative integers. If we ignore, for the moment, the restrictions on $h'$, $t$, and $u$, a particular solution of equation 3 corresponds to the placement of three addition signs in a row of fifteen ones. For instance, $$1 1 1 1 + 1 1 1 1 1 + 1 1 1 1 1 1 +$$ corresponds to the solution $h' = 4$, $t = 5$, $u = 6$, and $s = 0$, while $$1 1 1 + 1 1 1 1 + 1 1 + 1 1 1 1 1 1$$ corresponds to the solution $h' = 3$, $t = 4$, $u = 2$, and $s = 6$. Hence, the number of solutions of equation 3 in the non-negative integers is $$\binom{15 + 3}{3} = \binom{18}{3}$$ since we must select which three of the eighteen symbols (fifteen ones and three addition signs) will be addition signs.

However, we have counted solutions in which $h' > 8$, $t > 9$, or $u > 9$. We must exclude those solutions.

Suppose $h' > 8$. Then $h' \geq 9$. Let $h'' = h' - 9$. Then $h''$ is a non-negative integer. Substituting $h'' + 9$ for $h'$ in equation 3 yields \begin{align*} h'' + 9 + t + u + s & = 15\\ h'' + t + u + s & = 6 \tag{4} \end{align*} Equation 4 is an equation in the non-negative integers with $$\binom{6 + 3}{3} = \binom{9}{3}$$ solutions.

Suppose $t > 9$. Then $t \geq 10$. Let $t' = t - 10$. Then $t'$ is a non-negative integer. Substituting $t' + 10$ for $t$ in equation 3 yields \begin{align*} h' + t' + 10 + u + s & = 15\\ h' + t' + u + s & = 5 \tag{5} \end{align*} Equation 5 is an equation in the non-negative integers with $$\binom{5 + 3}{3} = \binom{8}{3}$$ solutions.

By symmetry, there are also $\binom{8}{3}$ solutions in which $u > 9$.

Notice that since $9 + 10 = 19 > 15$, at most one of the conditions $h' \leq 8$, $t \leq 9$, and $u \leq 9$ can be violated simultaneously in equation 3. Hence, the number of solutions of equation 3 subject to those restrictions is $$\binom{18}{3} - \binom{9}{3} - 2\binom{8}{3}$$

I think of these sorts of problems geometrically. Here, you can imagine $x$, $y$, and $z$ as describing the physical position of points on a cubic lattice. (It's not quite a cube, since the $x$ dimension is shorter than the other two.)

The constraint $x+y+z\le16$ describes a plane that cuts this cube into two parts: the acceptable part and the unacceptable part.

We can't immediately convert 'volume' to 'number of points in the cube', but this still guides the intuition of how to step through the problem and count correctly. For example, one might go slice by slice (in the $x$ direction, since that's the one that's distinct). For the slice $x=1$, the acceptable region is $0\le y\le9$ and $0\le z\le \mathrm{min}(9,15-y)$. That's a rectangle of size 10 by 7 (all $y$, $z$ from 0 to 6), a rectangle of size 7 by 3 ($z$ from 7 to 9, $y$ from 0 to 6), and then three points left over. So that's 94 for the $x=1$ slice, and now we can repeat the process for all possibilities of $x$.

We might have seen this more easily by realizing that there are 100 points in the slice and 6 points were excluded, and that's what I recommend you do going forward, as it's easier to calculate the new exclusion region (triangular numbers) than it is to calculate the new inclusion region. This longer method should make the explanation more clear, though.

Let $k\in\{1,2,...,16\}$ a fixed number. If you count the number of triplets $(x,y,z)$ such that $x+y+z=k$, say $S_k$, then you are searching for $S_0+S_1+...+S_{16}$,

Now, by generating functions method, we use the polinomyal $p(x)=(x+x^2+...+x^9)(1+x+x^2+...+x^9)^2$ and we want to find the coefficient of $x^k$.

But

$\begin{eqnarray} p(x)&=&(x+x^2+...+x^9)(1+x+x^2+...+x^9)^2\\ &=&x\left(\frac{1-x^{9}}{1-x}\right)\left(\frac{1-x^{10}}{1-x}\right)^2\\ &=&x(1-x^9)(1-x^{10})^2(1-x)^{-3}\\ &=&x(1-x^{9})(1-2x^{10}+x^{20})\sum_{r=0}^\infty\binom{2+r}{2}x^r \end{eqnarray}$

Now, it is easy to see that for $k=1,...,9$, the coefficient of $x^k$ is $\binom{2+k-1}{2}=\binom{k+1}{2}$.

For $k=10$, the coefficient is $\binom{2+9}{2}-\binom{2+0}{2}=\binom{11}{2}-1$

For $k=11,...,16$, the coefficient is $\binom{2+k-1}{2}-2\binom{2+k-11}{2}-\binom{2+k-10}{2}=\binom{k+1}{2}-2\binom{k-9}{2}-\binom{k-8}{2}$.

$\begin{eqnarray} S_0+...+S_{16}&=&\sum_{k=1}^{16}\binom{k+1}{2}-1-2\sum_{k=11}^{16}\binom{k-9}{2}-\sum_{k=11}^{16}\binom{k-8}{2}\\ &=&816-1-2*56-83\\ &=&620 \end{eqnarray}$