0

How many 3 digit numbers exist such that the sum of their digits equals 12? I ran a little program and found that there are $66$ of such numbers.

I feel that this type of problem is similar in style to that of the Diophantine equation $ax+by=c$ except in this case $a+b+c=12$ where $a,b,c,$ are positive integers.
The only problem is that I don't know how properly solve a Diophantine equation or for that matter even solve one without brute force and tears.

I thought about making a table and finding a pattern between the number of possible orders by increasing the hundreds digit by 1 and then counting.

Ian L
  • 889
  • For this problem, cases works nicely, For first digit $k$, where $k\ge 3$, there are $13-k$ possibilities. The situation is a little different for $k=1$ and $k=2$. – André Nicolas Jul 25 '16 at 01:02

2 Answers2

2

We can solve this with the stars and bars method.

We need to find all non-negative solutions $a+b+c=11$ with $a\leq 8$ and $b,c\leq 9$. (the number is going to be $\overline{(a+1)bc}$).

To do this we first find all the solutions disregarding the upper bound on a,b,c.

This is simple with stars and bars. There are $11$ stars and $2$ bars, so $\binom{13}{2}=78$.

We now need to subtract the solutions in which $a\geq 9,b\geq 10$ and $c\geq 10$.(but none of them happen at the same time, so it is easy)

There are $6$ when $a\geq9$, $3$ when $b\geq 10$ and $3$ when $c\geq 10$.

Therefore the final answer is $78-6-3-3=66$

Asinomás
  • 105,651
2

$\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

With the numbers $\ds{100,101,102,\ldots,997,998,999}$:

\begin{align} &\color{#f00}{\sum_{a = \color{#000}{\large 1}}^{9}\,\sum_{b = 0}^{9} \sum_{c = 0}^{9}\delta_{a + b + c,12}}\,\,\, = \sum_{a = 1}^{9}\sum_{b = 0}^{9}\sum_{c = 0}^{9}\,\,\oint_{\verts{z}\ =\ 1^{-}} \,\,\,{1 \over z^{13 - a - b - c}}\,\,\,{\dd z \over 2\pi\ic} \\[5mm] = &\ \oint_{\verts{z}\ =\ 1^{-}}\,\, {1 \over z^{13}}\pars{\sum_{a = 1}^{9}z^{a}} \pars{\sum_{\ell = 0}^{9}z^{\ell}}^{2}\,{\dd z \over 2\pi\ic} \\[5mm] = &\ \oint_{\verts{z}\ =\ 1^{-}}\,\,{1 \over z^{13}}\, \pars{z\,{z^{9} - 1 \over z - 1}}\,\pars{z^{10} - 1 \over z - 1}^{2} \,{\dd z \over 2\pi\ic} \\[5mm] = &\ \oint_{\verts{z}\ =\ 1^{-}}\,\, {\pars{z^{9} - 1}\pars{z^{10} - 1}^{2} \over z^{12}}\,{1 \over \pars{z - 1}^{3}} \,{\dd z \over 2\pi\ic} \\[5mm] = &\ \oint_{\verts{z}\ =\ 1^{-}}\,\, {z^{29} - z^{20} -2z^{19} + \color{#f00}{2z^{10}} + \color{#f00}{z^{9}} - \color{#f00}{1} \over z^{12}} \sum_{k = 0}^{\infty}{-3 \choose k}\pars{-1}^{k + 1}\,\,z^{k} \,{\dd z \over 2\pi\ic} \\[5mm] = &\ 2{-3 \choose 1} - {-3 \choose 2} - {-3 \choose 11} = -2{3 \choose 1} - {4 \choose 2} + {13 \choose 11} = -2 \times 3 - 6 + 78 = \color{#f00}{66} \end{align}

Felix Marin
  • 89,464