• Support PF! Buy your school textbooks, materials and every day products Here!

Discrete Math/Combinatorics Question

  • Thread starter Rockoz
  • Start date
  • #1
29
0

Homework Statement


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?


Homework 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.


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.
 

Answers and Replies

  • #2
881
40
The approach to part (a) seems correct :approve:

For the second one you need to use the same approach adding all the 5 cases.
 

Related Threads on Discrete Math/Combinatorics Question

  • Last Post
Replies
4
Views
995
  • Last Post
Replies
9
Views
473
  • Last Post
Replies
3
Views
515
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
1
Views
879
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
0
Views
810
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
6
Views
1K
Top