Stars and Bars Question

[westin]

How many four digit numbers have the sum of the digits equal to 31? Answer is 56. I found below solution from the web but not quite understands the reason.

"We need a sum of 31 and I've seen many people post solutions, which involved lot of inclusion. So I'll share a simple trick. If the sum of digits is close to max possible value, then start from the max possible value.

For example, in this question first imagine that you have given 9 to each of the four digits.
Now, the total will 36 but we required 31, so we need to take back 5.
The number of ways of taking 5 back from 4 boxes (places of the number) must be same as the number of ways of distributing 5 to 4 boxes.
Which would be
(5+4-1)C(4-1) =8C3 =56"

MY questions is why the number of ways taking 5 back from 4 boxes must be same as number of ways distributing 5 to 4 boxes. Can someone explain the reason and let me understands it more? or is there a more easy way to approach this question in a star and bars way?

Thanks!!!

 

[westin]

Also, why start from the max possible value 36? Don't quite get the logic behind the approach.... Thank you in advance for the help!!!

 

[Dr.Peterson]

How many four digit numbers have the sum of the digits equal to 31? Answer is 56. I found below solution from the web but not quite understands the reason.

"We need a sum of 31 and I've seen many people post solutions, which involved lot of inclusion. So I'll share a simple trick. If the sum of digits is close to max possible value, then start from the max possible value.

For example, in this question first imagine that you have given 9 to each of the four digits.
Now, the total will 36 but we required 31, so we need to take back 5.
The number of ways of taking 5 back from 4 boxes (places of the number) must be same as the number of ways of distributing 5 to 4 boxes.
Which would be
(5+4-1)C(4-1) =8C3 =56"

MY questions is why the number of ways taking 5 back from 4 boxes must be same as number of ways distributing 5 to 4 boxes. Can someone explain the reason and let me understands it more? or is there a more easy way to approach this question in a star and bars way?

Thanks!!!

You might think of it this way. The digit-sum for 9999 is 36. If you make any number whose digit-sum is 5 and subtract it from 9999, the result will be a number that fits the requirement of the problem. For example, if you subtract 1022 from 9999 you get 8977, whose digit-sum is 31. His "taking back" is the same as my "subtracting".

There's one thing to be careful with, however: In the original problem, we would not count a number that started with 0, because it wouldn't be a 4-digit number. (Do you see why that isn't a problem, though?) On the other hand, in our new problem (digit-sum of 5), we need to count numbers that start with zero. Luckily, that just makes it easier, not harder.

Also, why start from the max possible value 36? Don't quite get the logic behind the approach.... Thank you in advance for the help!!!

Try doing the same thing with a smaller number, and see what happens! This is just something you discover with experience: Sometimes turning a problem inside-out in some way helps (and sometimes it doesn't).

 

[pka]

How many four digit numbers have the sum of the digits equal to 31? Answer is 56. I found below solution from the web but not quite understands the reason.
MY questions is why the number of ways taking 5 back from 4 boxes must be same as number of ways distributing 5 to 4 boxes. Can someone explain the reason and let me understands it more? or is there a more easy way to approach this question in a star and bars way?

To westin: before I start an explication here is a book you really should have MATHEMATICS OF CHOICE by Ivan Niven A good used paperback in good condition would be ideal. How ways can we solve the equation $a+b+c+d+x+y+z=147$ in the non-negative integers?
Well that is the same as asking: how many ways are there to put $1047$ identical 1's, balls, or stares into six distinct cells.
To model the cells we can use only five bars: $\mathop {\_\_}\limits_a |\mathop {\_\_}\limits_b |\mathop {\_\_}\limits_c |\mathop {\_\_}\limits_x |\mathop {\_\_}\limits_y |\mathop {\_\_}\limits_z$.
If you understand that the name $MISSISSIPPI$ can be rearranged in $\dfrac{11!}{(4!)^2(2!)}$ ways then you understand how five identical bars and $147$ identicall balls can be rearranged in $\dfrac{[(6-1)+147)!}{(147!)(5!)}$ ways. Now that counts all the ways to place the balls in the boxes. But some could be empty. If we want ask that the solutions be in the positive integers (at least one) go ahead an put one ball is each box now the answer is $\dfrac{[(6-1)+14{\color{blue}\Large 1})!}{(147!)(5!)}$ Why change the 7 to 1? In we need for no box to contain more than fifty balls, what would we have to do?

 

[westin]

Hi Dr.Peterson, I understand now. I see you can have a 0 in the new problem because you aren't solving for the digits, you're solving number of ways you can make 5 using 4 numbers. Thank you!!!!!!

 

[Dr.Peterson]

Hi Dr.Peterson, I understand now. I see you can have a 0 in the new problem because you aren't solving for the digits, you're solving number of ways you can make 5 using 4 numbers. Thank you!!!!!!

More than that: in the original problem, not having a 0 in the first place isn't a limitation, because you couldn't fit a sum of 31 in only three digits anyway.

On the other hand, if the number were not 31 but, say, 25, you would have to pay more attention to details. (This would make the "take back" trick more messy, too, because each digit would have to be restricted.)

 

[westin]

understood. because the difference is more than 10 and each digit can only lies between 0-9. in this scenario, I think we need to do a case by case computation which is messy too. I think I understand more about how stars and bars work, however, sometimes when the question changes slightly then it mess up my thinking. i guess i need to do more. thank you for the help.

 

[Dr.Peterson]

This is really messing with my brain. Can someone give a clue on how to easily solve this

Clues have been given! (But it may still not be easy.)

In order to get help appropriate to you, you'll need to show us where you are in your understanding of the problem, so we can tell what sort of clue you are lacking. See here:

Posting Guidelines (Summary)

Welcome to our tutoring boards! :) This page summarizes main points from our posting guidelines. As our name implies, we provide math help (primarily to students with homework). We do not generally post immediate answers or step-by-step solutions. We don't do your homework. We prefer to help...

www.freemathhelp.com