Use the separator method.Chaitanya_1986 wrote:How many positive integers less than 10,000 are there in which sum of digits equals 5?
(a) 31
(b) 51
(c) 56
(d) 62
(e) 93
The separator method can used to count the number of ways to distribute identical elements.Chaitanya_1986 wrote:Hi Mitch,
Thanks a lot for your explanation.
Could you please tell me When can we use a separator method? and in which type of problems can we use this method.
If you revisit my post above, you'll note that I've edited the question to make its intention clearer.prakhag wrote:Hi Mitch:
Further on the example that you've given below, let's say I want to do this using normal P n C.
Case 1) One child catches 2 balls and remaining 2 children catch 1 ball each.
Case 2) One child catches 3 balls and out of remaining 2 children, 1 catches 1 ball.
Case 3) One child catches all 4 balls.
So, for Case 1): Choosing 1 child out of 3 to catch 2 balls - 3C1. This child can catch the ball in 4!/2! ways
Choosing 2 children out of 2 to catch 1 ball each - 2C2*1
Total no. of ways = 3C1*4!/2!*2C1*1 = 36
Similarly we can calculate combinations for Case 2 and 3. Of course my answer doesn't match yours but can you please point out what's wrong with this approach?
GMATGuruNY wrote:Use the separator method.Chaitanya_1986 wrote:How many positive integers less than 10,000 are there in which sum of digits equals 5?
(a) 31
(b) 51
(c) 56
(d) 62
(e) 93
Let the 5 digits whose sum is 5 = DDDDD.
Any division of these five D's will yield an expression that represents a 5-digit integer, the sum of whose digits is 5:
DDDDD = 5.
DDDD D = 41.
D DDD D = 131.
To be less than 10,000, the integer can have at most 4 digits.
Thus, the five D's can be separated at most into 4 groups. For example:
D D D DD = 1112.
Thus, there are at most 3 separators dividing the five D's.
Let the 3 separators = |||.
Thus:
|||DDDDD = 5.
||DDDD|D = 41.
|D|DDD|D = 131.
D|D|D|DD = 1112.
Thus, to count the number of integers, we need to count the number of ways to arrange DDDDD|||.
Number of ways to arrange DDDDD||| = 8!/(5!3!) = 56.
The correct answer is C.
The separator method is used to count the number of ways in which identical elements can be distributed.apex231 wrote:Hi Mitch, won't the sequence of numbers matter in this case? For e.g. (14,41), (23,32), (1112, 1211,1121..)?
Thanks
GMATGuruNY wrote:Use the separator method.Chaitanya_1986 wrote:How many positive integers less than 10,000 are there in which sum of digits equals 5?
(a) 31
(b) 51
(c) 56
(d) 62
(e) 93
Let the 5 digits whose sum is 5 = DDDDD.
Any division of these five D's will yield an expression that represents a 5-digit integer, the sum of whose digits is 5:
DDDDD = 5.
DDDD D = 41.
D DDD D = 131.
To be less than 10,000, the integer can have at most 4 digits.
Thus, the five D's can be separated at most into 4 groups. For example:
D D D DD = 1112.
Thus, there are at most 3 separators dividing the five D's.
Let the 3 separators = |||.
Thus:
|||DDDDD = 5.
||DDDD|D = 41.
|D|DDD|D = 131.
D|D|D|DD = 1112.
Thus, to count the number of integers, we need to count the number of ways to arrange DDDDD|||.
Number of ways to arrange DDDDD||| = 8!/(5!3!) = 56.
The correct answer is C.
Number of separators = Maximum number of distributions - 1.nafiul9090 wrote:just one thing to clear...how do we get the number of separators????
Hi!GMATGuruNY wrote:The separator method is used to count the number of ways in which identical elements can be distributed.apex231 wrote:Hi Mitch, won't the sequence of numbers matter in this case? For e.g. (14,41), (23,32), (1112, 1211,1121..)?
Thanks
GMATGuruNY wrote:Use the separator method.Chaitanya_1986 wrote:How many positive integers less than 10,000 are there in which sum of digits equals 5?
(a) 31
(b) 51
(c) 56
(d) 62
(e) 93
Let the 5 digits whose sum is 5 = DDDDD.
Any division of these five D's will yield an expression that represents a 5-digit integer, the sum of whose digits is 5:
DDDDD = 5.
DDDD D = 41.
D DDD D = 131.
To be less than 10,000, the integer can have at most 4 digits.
Thus, the five D's can be separated at most into 4 groups. For example:
D D D DD = 1112.
Thus, there are at most 3 separators dividing the five D's.
Let the 3 separators = |||.
Thus:
|||DDDDD = 5.
||DDDD|D = 41.
|D|DDD|D = 131.
D|D|D|DD = 1112.
Thus, to count the number of integers, we need to count the number of ways to arrange DDDDD|||.
Number of ways to arrange DDDDD||| = 8!/(5!3!) = 56.
The correct answer is C.
Since in the problem above the sum of the digits must be 5, the separator method can be used to count the number of ways in which the 5-unit sum (DDDDD) can be distributed among the 1,2,3 or 4 digits.
To illustrate:
|D|DD|DD = a distribution of 0-1-2-2, representing the number 122.
|DD|D|DD = a distribution of 0-2-1-2, representing the number 212.
|DD|DD|D = a distribution of 0-2-2-1, representing the number 221.
Notice that the distributions above account for all the different ways in which the digits 1,2,2 can be ordered in a 3-digit integer.
Thus, by using the separator method to count all the different ways in which the 5-unit sum can be distributed, we account for every possible sequence of digits.
