How many integers are there between 1 and 1000000 whose digits add to 25?
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 added a summation to the formula given by Garrett Clarke for k = 3 t o 7 in this problem . Obviously, I generated a loop summation for it in python. How did you do it? What's the mathematical approach?
Well the main reason why I posted this problem was to see if anyone could come up with a good solution to it.
The method I used is the same method used in my solution to the 'Waiting for the bathroom' problem that coincidentally you linked to in your solution.
So the generating functions method which I used for this question is as follows: The digits of 1000000 don't add to 25 so 1000000 can be ignored and only the numbers 1 to 999999 need to be considered. These numbers can all be written as a 6 digit number, perhaps with zeros at the beginning so for example 38 would become 000038. We can include 000000 as well as this will not affect the answer because the digits dont add to 25 anyway. This means that we need to choose a number between 0 and 9 for each of the six digits so that the six digits add to 25. The generating function for this is:
( 1 + x + x 2 + x 3 + x 4 + x 5 + x 6 + x 7 + x 8 + x 9 ) 6
and so the answer is the coefficient of x 2 5 in this expansion of this. Using wolfram alpha to work out the expansion, the coefficient of x 2 5 is 53262. As mentioned in my solution to the other problem, the obvious flaw in this method is that wolfram alpha has to be used (or you could spend a very long time multiplying it out manually!) but at least this shows a mathematical representation of why 53262 is the answer.
Log in to reply
I followed the same method in that problem too. And it's honestly no good.
Problem Loading...
Note Loading...
Set Loading...
@Melissa Quail , actual is it possible to solve it without using Wolfram Alpha. As you have say in the comment below the answer is the coefficient of x 2 5 in this expansion of ( 1 + x + . . . + x 9 ) 6 . Now:
( 1 + x + x 2 + . . . + x 9 ) 6 = ( 1 − x ) 6 ( 1 − x 1 0 ) 6 and so, using Binomial Theorem we could write:
( 1 − x 1 0 ) 6 = k = 0 ∑ 6 ( k 6 ) ( − 1 ) k x 1 0 k and using Negative Binomial Theorem ( 1 − x ) − 6 = s = 0 ∑ ∞ ( s 5 + s ) x 6
Putting all together:
( 1 + x + x 2 + . . . x 9 ) 6 = s = 0 ∑ ∞ k = 0 ∑ 6 ( k 6 ) ( s 5 + s ) ( − 1 ) k x 1 0 k + s
Now 1 0 k + s = 2 5 when ( k , s ) = ( 0 , 2 5 ) ∧ ( 1 , 1 5 ) ∧ ( 2 , 5 ) and so the coefficient is:
( 0 6 ) ( 2 5 3 0 ) − ( 1 6 ) ( 1 5 2 0 ) + ( 2 6 ) ( 5 1 0 ) = 5 3 2 6 2 .