0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Please show us your calculations so that we can see what you did and where you ran into difficulties. $\endgroup$ – N. F. Taussig Jul 23 '16 at 12:12
  • $\begingroup$ 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 $\endgroup$ – G_Derek007 Jul 23 '16 at 12:21
  • $\begingroup$ 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. $\endgroup$ – N. F. Taussig Jul 23 '16 at 12:23
  • $\begingroup$ I have changed the question to 12 however it should still be the same concept $\endgroup$ – G_Derek007 Jul 23 '16 at 12:29
  • $\begingroup$ 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? $\endgroup$ – N. F. Taussig Jul 23 '16 at 12:36
3
$\begingroup$

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$$

$\endgroup$
  • 1
    $\begingroup$ It became a lot more clearer thanks! Is it too much to ask if its possible to derive a general solution? $\endgroup$ – G_Derek007 Jul 23 '16 at 13:20
  • 1
    $\begingroup$ 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 $\endgroup$ – G_Derek007 Jul 23 '16 at 13:35
  • 1
    $\begingroup$ @user295641 Yes, there are 70 3 digit numbers whose digits sum to 14. $\endgroup$ – PM 2Ring Jul 23 '16 at 13:38
  • $\begingroup$ 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. $\endgroup$ – N. F. Taussig Jul 23 '16 at 13:39
  • $\begingroup$ @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)$ $\endgroup$ – PM 2Ring Jul 23 '16 at 14:09
2
$\begingroup$

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$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.