How many integers from 1 through 99,999 is the sum of their digits = 9?

[mr_coffee]

Wow, I'm totally lost on where to start for this one.
In this chapter we have been working with r-combinations with repeition allowed and using the form of(r + n - 1)
(r )
Where n stands for categories, so if you had 4 categories u would use 3 bars to break up the categories. And r chocies.

For example, I think I did a simplier problem that might help me:

Find how many solutions there are to given equation that satisfy the given condition.y_1 + y_2 + y_3 + y_4 = 30, each y_i is an integer that is at least 2.

So y_i >= 2.

There are 4, y's, so you have 4 categories, thus 3 bars to split up the categories. I will represent the sum by putting x's in each category so the end result equals 30, this will help me visualize the combinations.

There are already 2 x's in each category to start with before I even begin to place any x's in, so that means 30-8 = 22. So i have 22 x's i can distribute.
xxxxxxxxxx | xxxxxxxxxx | x | x
I have 22 x's here, + 8 already in there = 30.

So apply the formula, I have (22 + (4-1)) choose (22)
= 25 choose 22
= 25!/(22!3!) = 2300.Now can I apply this technique to the above problem? If so I really don't see how...

I could do like

x_1 + x_2 + x_3 +...+ x_99999 = 9

but that means I would have 99,999 - 1 categories, and 9 x's to distrubute in those 99,998 categories anywhere I want i guess.

So with that logic the combination would look like:
(9 + 9998) choose 9
= (10007) choose 9
= (10007)!/[9!(9998)!]
= undefined by the all mighty ti-89

which can't be right...any idea where I'm messing up?

Thanks

 

[mattmns]

I think you can apply the same technique but I think you are doing it incorrectly. Consider this: We are looking at the integers from 1 to 99,999 so let us look at numbers of the following form: x_{1}x_{2}x_{3}x_{4}x_{5} where x_{1}, is the first digit of our number, x_{2} is the second, and so on, also 0 \leq x_{i} \leq 9 for each x_{i} since each digit can vary from 0 to 9 (note that 00004 = 4).

Using this, what would the equation be? Keep in mind that we want the sum of all the digits to equal 9. Then what would be the number of solutions to this equation? (You should get 715)

Note that if the digits summed up to a number more than 9 we would have to use a different technique, for example we could use the inclusion-exclusion principle.

 

[marcmtlca]

I believe the question is only asking for the number of solutions to: x_1+x_2+x_3+x_4+x_5=9 with 0 \le x_i \le 9,x_i \in \bf{N}.

 

[mr_coffee]

thanks for the reply guys, I think marc got that right when he said x1 + x2 + x3 + x4 + x5 = 9.

And it matches what you said matt I think. But I'm getting a slightly larger answer than yours matt. Here is my work:
x_1+x_2+x_3+x_4+x_5=9

So you have 5 categories, thus you can use 4 bars to reprsent that. You also only have 9 x's to distrubute into those 5 categories. So an example of one would be:

xx|xxx|xx|x|x

So you have 9 x's and 4 |'s
then apply the formula:
(9+4) choose 9 = 13 choose 9 = 13!/(9!4!) = 171600 solutions.

Any idea where I messedup?

 

[mattmns]

Yep it matches what I said. You did everything right, I am not sure how you got 171600; when I compute 13 choose 9 I get 715, and when I do 13!/(9!4!) I also get 715, so I am not sure what you did there. However, I would just leave the answer as 13 choose 9.

 

[mr_coffee]

Thanks matt, i was using the calculator on windows lol i did it by hand and got what u got, thanks again for the help!

 

[devious_]

Aren't they simply those integers divisible by 9? So there should be 99,999/9 of them.

 

[marcmtlca]

99,999 is divisible by 9 but the digits sum to 45.

 

[Holla&Cuss]

Not quite...

I believe the question is only asking for the number of solutions to: x_1+x_2+x_3+x_4+x_5=9 with 0 \le x_i \le 9,x_i \in \bf{N}.

That should give you 715 but that is not the full answer!

The question asks for all integers from 1 through 99999. Your solutions are only integers 10000-99999. You'd also need to do:
x_1+x_2+x_3+x_4=9 with 0 \le x_i \le 9,x_i \in \bf{N}
(Should give you 220)
x_1+x_2+x_3=9 with 0 \le x_i \le 9,x_i \in \bf{N}
(Should give you 55)
x_1+x_2=9 with 0 \le x_i \le 9,x_i \in \bf{N}
(Should give you 10)
x_1=9 with 0 \le x_i \le 9,x_i \in \bf{N}
(Should give you 1)

Then simply add them together:
715+220+55+10+1=1001 (Your CORRECT Answer!).

Hope this helps!

 

[Panda]

No because within
X1+X2+X3+X4+X5=9

0+9+0+0+0 is a valid combination

So the answer is 715

 

[Holla&Cuss]

Oops! I stand corrected.

 

[HallsofIvy]

Aren't they simply those integers divisible by 9? So there should be 99,999/9 of them.

You are thinking of "casting out 9s": add the digits and if the sum is greater than 9, repeat. Hear the condition is just "the sum of digits is 9". As marcmtlca said, 99,999 itself is divisible by 9 but its sum of digits is 45. Of course, 4+ 5= 9.