How many 3 digit numbers that the sum of their digits equals 12?

How many positive 3-digit numbers exist such that the sum if their digits equals 12?

A) 54

B) 61

C) 64

D) 65

E) 66

I believe the answer is E.

Online problems state that is a stars and bars problem, however using the (n-1,k-1)/n-1C k-1 and (n+k-1,n)/n+k-1 C n formulas do not yield any of the answer choices.

Using (n-1,k-1) I get 55 and using (n+k-1,n) I get 91. Fifty five appears to be the closest answer.

I do not know how to do the inclusion method to remove results such as 066.

• Please show us your calculations so that we can see what you did and where you ran into difficulties. – N. F. Taussig Jul 23 '16 at 12:12
• Online problems state that is a stars and bars problem, however using the n-1 C k-1 and n+k-1 C n formulas do not yield 54. I get 190 from n+k-1 C n and 139 from n-1 C k-1 – G_Derek007 Jul 23 '16 at 12:21
• Please edit your question to show us exactly what you did. I suspect you have not taken into account the restrictions on the hundreds digit, tens digit, and units digit. – N. F. Taussig Jul 23 '16 at 12:23
• I have changed the question to 12 however it should still be the same concept – G_Derek007 Jul 23 '16 at 12:29
• If I read your work correctly, you used the formula for solutions in the positive integers to obtain $\binom{12 - 1}{3 - 1} = \binom{11}{2} = 55$ and for solutions in the non-negative integers to obtain $\binom{12 + 3 - 1}{3 - 1} = \binom{14}{2} = 91$. Is that what you did? – N. F. Taussig Jul 23 '16 at 12:36

A three-digit positive integer has the form $100h + 10t + u$, where the hundreds digit $h$ satisfies the inequalities $1 \leq h \leq 9$, the tens digit $t$ satisfies the inequalities $0 \leq t \leq 9$, and the units digit $u$ satisfies the inequalities $0 \leq u \leq 9$. Therefore, we wish to determine the number of solutions of the equation $$h + t + u = 12 \tag{1}$$ subject to these restrictions.

If we let $h' = h - 1$, then $0 \leq h' \leq 8$. Substituting $h' + 1$ for $h$ in equation 1 yields \begin{align*} h' + 1 + t + u & = 12\\ h' + t + u & = 11 \tag{2} \end{align*} Equation 2 is an equation in the non-negative integers. A particular solution corresponds to the placement of two addition signs in a row of eleven ones. There are $$\binom{11 + 2}{2} = \binom{13}{2}$$ such solutions since we must choose which two of the thirteen symbols (eleven ones and two addition signs) will be addition signs.

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

Suppose $h' > 8$. Then $h'$ is an integer satisfying $h' \geq 9$. Let $h'' = h' - 9$. Then $h'' \geq 0$. Substituting $h'' + 9$ for $h'$ in equation 2 yields \begin{align*} h'' + 9 + t + u & = 11\\ h'' + t + u & = 2 \tag{3} \end{align*} Equation 3 is an equation in the non-negative integers. Since a particular solution corresponds to the placement of two addition signs in a row of two ones, it has $$\binom{2 + 2}{2} = \binom{4}{2}$$ solutions.

Suppose $t > 9$. Then $t$ is an integer satisfying $t \geq 10$. Let $t' = t - 10$. Substituting $t' + 10$ for $t$ in equation 2 yields \begin{align*} h' + t' + 10 + u & = 11\\ h' + t' + u & = 1 \tag{4} \end{align*} Equation 4 is an equation in the non-negative integers with $\binom{3}{2} = 3$ solutions, depending on which variable is equal to $1$. By symmetry, there are also three solutions in which $u' > 9$. No two of these restrictions cannot be violated simultaneously since $9 + 10 = 19 > 12$. Thus, the number of three-digit positive integers with digit sum $12$ is $$\binom{13}{2} - \binom{4}{2} - 2\binom{3}{2} = 66$$

• It became a lot more clearer thanks! Is it too much to ask if its possible to derive a general solution? – G_Derek007 Jul 23 '16 at 13:20
• I believe I derived one already to be sure though if the sum of the digits were 14 it would be 70? The formula is S=sum of digits D=number of digits (S+D-1,D-1) - (S+D-1-9,D-1) - 2*(S+D-1-9-1,D-1)it should work for 3 digit numbers, which is what I need – G_Derek007 Jul 23 '16 at 13:35
• @user295641 Yes, there are 70 3 digit numbers whose digits sum to 14. – PM 2Ring Jul 23 '16 at 13:38
• That would be a rather long answer. For $h + t + u = k$, where $1 \leq k \leq 9$, you can stop after finding the solution to equation 2 with $k$ replacing $12$. For $h + t + u = 10$, you can stop after equation $3$ with $10$ replacing $12$. For $h + t + u = k$, where $11 \leq k \leq 18$, the same procedure will work if you replace $12$ by $k$. For $18 \leq k \leq 27$, we require the Inclusion-Exclusion Principle because two or more restrictions can be violated simultaneously in equation 2. – N. F. Taussig Jul 23 '16 at 13:39
• @user295641 You have an off-by-one error in that formula; I think you mean: $(S+1, 2) - (S-8, 2) - 2*(S-9, 2)$. However, that formula only works for $9 \le S \le 19$. Note that there is a symmetry. Let $f(S, D)$ be the count of $D$ digit numbers that sum to $S$. Then $f(9D+1-S, D) = f(S, D)$ – PM 2Ring Jul 23 '16 at 14:09

Here's a less algebraic way to look at it. .

Start by putting $1$ into the first cell, ${\boxed 1}\Large\boxed.\boxed.$, so you now only need a sum of $11$,
with the constraints that you can't put $\ge9$ in the first cell, and $\ge10$ in the other two.

Apply stars and bars, subtracting solutions that violate the constraints.

Since it is not possible to violate the constraint in more than one cell, $$ans = \binom{13}2 - \binom{13-9}2 - 2\binom{13-10}2 = 66$$