13
$\begingroup$

Well, I've been almost losing my mind over this one.

The question is: How many integers on the interval $[3000, 8000]$ have a digit sum of 20?

Well, the first thing I did was separating to groups according to the first digit. and then:

3- A+B+C=17

4- A+B+C=16

5- A+B+C=15

6- A+B+C=14

7- A+B+C=13

Now my main problem is: Since A, B, and C are digits, it means that they are on the interval $[0, 9]$. How do I take that restriction into account?

$\endgroup$
  • 1
    $\begingroup$ If A is 0, B needs to be atleast 4; if A is 1; B must be greater than 3 and you get the combinations. $\endgroup$ – hjpotter92 Mar 24 '13 at 15:46
  • $\begingroup$ It still didn't answer how do you take all the rest of the restrictions into account. $\endgroup$ – StationaryTraveller Mar 24 '13 at 16:10
  • $\begingroup$ Since you already grouped them from 3k to 8k; group a little more? $\endgroup$ – hjpotter92 Mar 24 '13 at 16:12
  • $\begingroup$ So the best way is just counting my way out? Sounds... Inefficient. $\endgroup$ – StationaryTraveller Mar 24 '13 at 16:31
  • $\begingroup$ @TheAlchemist Inefficient this! Count[Total[IntegerDigits[#]] & /@ Range[3000, 8000], 20] *karate chop* $\endgroup$ – amr Mar 24 '13 at 18:21
12
$\begingroup$

Method 1: Using generating functions, you want the coefficient of $x^{20}$ in $$(x^3+x^4+ \ldots +x^7)(1+x+ \ldots +x^9)^3=\frac{x^3(1-x^5)(1-x^{10})^3}{(1-x)^4}$$

Equivalently, we drop the $x^3$ factor and look for the coefficient of $x^{17}$.

We have $(1-x)^{-4}=\sum_{i=0}^{\infty}{\binom{i+3}{3}x^i}$. Expanding $(1-x^5)(1-x^{10})^3$ and ignoring $x^n, n>17$ gives $(1-x^5)(1-3x^{10})=1-x^5-3x^{10}+3x^{15}$.

Finally the coefficient of $x^{17}$ is $$\binom{(17-0)+3}{3}-\binom{(17-5)+3}{3}-3\binom{(17-10)+3}{3}+3\binom{(17-15)+3}{3}$$

which easily evaluates to give $355$.

Method 2: As you might not be familiar with generating functions, here is a more elementary approach.

We proceed exactly as you did. If the 1st digit is $i$, then we have $A+B+C=20-i$. This gives $\binom{(20-i)+2}{2}$, but we have also counted those where $A, B, C$ are $\geq 10$. For those cases, exactly 1 of the digits is $\geq 10$. If it is $A$, we have $A=k=10, 11, \ldots , 20-i$. Then $B+C=20-i-k$, giving $21-i-k$ ways. The number of ways for $B, C$ are the same. Therefore we must subtract $3\sum\limits_{k=10}^{20-i}{(21-i-k)}=3\sum\limits_{j=1}^{11-i}{j}=3\frac{(11-i)(12-i)}{2}$.

Therefore the total number is

$$\sum_{i=3}^{7}{\left(\binom{(20-i)+2}{2}-3\frac{(11-i)(12-i)}{2}\right)}=355$$

$\endgroup$
  • $\begingroup$ Well, This is the best answer i could possibly get, Thank you. $\endgroup$ – StationaryTraveller Mar 24 '13 at 21:52

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.