1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Discrete Math/Combinatorics Question

  1. May 23, 2012 #1
    1. The problem statement, all variables and given/known data
    This question has two parts:

    a) How many integers are there between 100 and 1,000,000 with the property that the sum of their digits is equal to 6?

    b) How many integers are there between 100 and 1,000,000 with the property that the sum of their digits is less than 6?

    2. Relevant equations
    Theorem: The number of solutions in nonnegative integers of the equation
    x1 + x2 + . . . + xn = k

    is C(n+k-1,k) where C is for combination.

    3. The attempt at a solution

    part a) Here is how I tried to look at the problem. For integers between 100 and 1,000,000 we have integers of the form x1x2x3x4x5x6x7 where x1 + x2 + x3 + x4 + x5 + x6 + x7 = 6.
    We must have x1 (the first digit) be equal to zero since we are between 100 an 1,000,000 and the case where x1= 1 wouldn't matter to us anyways. The other digits can be from 0 through 9. So we are left with x2+x3+x4+x5+x6+x7 = 6. The <=9 part doesn't matter here since the highest any of these xi's can be is 6. We solve for the number of solutions to this equation to get the number of integers. Using the theorem above I solve this as C(6+6-1,6) = C(11,6).

    But I believe this is actually the answer for integers from 1-1,000,000 and so I have overcounted (I am including integers like 0000006). So I think what I can do here is subtract the integers from 1-100 whose digits add up to 6. For this we have integers of the form y1y2y3 where y1 = 0 and y2 and y3 can be 0 through 9. We have y2 + y3 = 6. Using the theorem above I have C(2 + 6 - 1,6) = C(7,6) integers.

    So I think the answer for part a is C(11,6) - C(7,6) = 455

    part b) I don't know how to approach this because of the less than part. Would I have to take this into cases (equal to 1,2,3,4,5) and then add these?

    Thank you very much for your time.
  2. jcsd
  3. May 24, 2012 #2
    The approach to part (a) seems correct :approve:

    For the second one you need to use the same approach adding all the 5 cases.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook