How many 3 digit numbers are there, whose sum of digits is not greater than 16 ?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
I would love to see an intuitive solution to this. I noticed that it had to do with the third diagonal of Pascal's triangle. The number of 3 digit numbers who's digit sum is no greater than n is sum of the triangular numbers up to n.
The general formula for even n LESS THAN 10 is
4 1 ∑ 2 n k 2
For odd n LESS THAN 10
4 1 ∑ 2 n − 1 k 2 + 2 n ( n + 1 )
When n is greater than 10 the pattern doesn't work since it would mean that a three digit could have one single digit as like a 10.
I don't know why it's like this however. I spent 5 minutes getting an answer and when I checked it, which took about an hour, I found this pattern.
I took the complement (it's symmetric) from 1 to 9 then brute force bashed 10 and 11, then subtracted that from 900.
Btw can someone verify that the answer isn't 618? Cuz that's what I had originally.
Log in to reply
The answer is confirmed to be 620, for verification run the Python solution I posted.
For lazy people -
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
Output -
1 2 |
|
https://www.youtube.com/watch?v=Z7QSzy6e-HA see this video for solution
1 2 3 4 5 6 7 8 9 10 11 12 |
|
Problem Loading...
Note Loading...
Set Loading...
I used the generating functions method: The first digit can be any number between 1 and 9 inclusive, represented by the polynomial:
( x 1 + x 2 + x 3 + x 4 + x 5 + x 6 + x 7 + x 8 + x 9 ) and the second and third digits can be between 0 and 9 inclusive, the choices for each digit represented by the polynomial:
( x 0 + x 1 + x 2 + x 3 + x 4 + x 5 + x 6 + x 7 + x 8 + x 9 )
So the generating function is:
( x 1 + x 2 + x 3 + x 4 + x 5 + x 6 + x 7 + x 8 + x 9 ) ( x 0 + x 1 + x 2 + x 3 + x 4 + x 5 + x 6 + x 7 + x 8 + x 9 ) 2 )
We are interested in the coefficients of the terms with a power of x that is no greater than 16 so we need to multiply out the brackets and find the coefficients (to multiply out the brackets you can use the multinomial theorem or just type it into wolfram alpha!). These coefficients(from x 1 6 to x 1 ) are:
66, 69, 70, 69, 66, 61, 54, 45, 36, 28, 21, 15, 10, 6, 3 and 1
Adding these coefficients gives us the answer 6 2 0 .