Very tricky counting problem

vipulgoyal wrote:Hi Brent,

how did you come up with

" We can extend this solution and conclude that the number of integers less than 1,000,000 in which the sum of the digits equals 8 will be 13C5"
OR
8c3 for less then 10000

though I got the explanation how 13c5 and 8c3 are yeilding desired answers, but how did we come up with 13c5 and 8c3

DISCLAIMER: This question type is likely beyond the scope of the GMAT

Okay, let's begin with 8c3 for less then 10000
Let's take eight Os: OOOOOOOO
Let's randomly choose 3 of these O's and replace them with lines.
For example: OO|O|O|O
By counting the O's between lines, we see that this scenario represents the number 2111
Similarly, O|OO|O|O represents the number 1211, O||OOO|O represents the number 1031, and |O||OOOO represents the number 0104 (104)
In each selection, five O's remain, so the sum of the digits will always be 5.
So, we can select 3 O's from 8 O's in 8C3 ways (56 ways)

IMPORTANT: We want a 1-, 2-, 3- or 4-digit number (i.e., less than 10,000) such that the digits add to 5.
This is accomplished in (5 + 4 - 1)C(4 - 1) ways (8C3 ways)


Now let's deal with: the number of integers less than 1,000,000 in which the sum of the digits equals 8 will be 13C5
We want a 1-, 2-, 3-, 4-, 5-, or 6-digit number (i.e., less than 1,000,000) such that the digits add to 8.
This is accomplished in (8 + 6 - 1)C(6 - 1) ways (13C5 ways)

Cheers,
Brent

tanvis1120 wrote:What is insert stick and separator technique?

See the above posts.

Cheers,
Brent