You are Here: Home >< Maths

# Awful discrete question... watch

Announcements
1. The question as it came is in blue, and the solutions as they were given are in red. However there are parts I do not understand, and I shall write in black. All question I have will be in green. I hope this makes sense...

How many numbers in the range 1 to 1 000 000 inclusive have a sum of (decimal) digits (a) = 5 (b) <10 (c) = k (for a general fixed value of k)?

a) Consider:

This is found by where

They got the same in the solution but added: Note that this is valid since all digits are bounded above by 9 which is greater than 5 From what I understand of this statement, I think that it is saying, each digit is only one digit (eg 10 is two digits, 1 and 0), so the question can be answered in this way. Is my understanding of this final statement correct??

b) using a) it is easy to see that the answer is: Where the 1 takes into account the number 1 000 000.

They have the same solution as I do. there is no problem with this question.

c) Now I have not managed to get an answer to c) however I do have the solution, and I will write it in red, but it is quite long, and I need it explaining if that is ok.

Solution: "The values k> 9 are more complicated because we have an upper limit of 9 for each of the digits, so we can not simply look at unrestricted sums of non negative numbers adding to k. we can also observe that there are no solutions for k>54 (=6x9).

Also not that, given a particular number less than 1 000 000, it has a complimentary one got by taking each digit and replacing it by 9 - the value of that digit (to make this work you need to pad each number out by leading zeros if necessary so that it is six digits long).

Thus if we know the answer for a particular value of k, we must get the same answer for the value 54 - k (except that we must make an adjustment for k = 1 because the number 1 000 000 is exceptional to this argument).

Consider: . Then the number of non-negative 6 compositions of k is , but some of these may have summands greater than 9.

Thus we need to remove all those compositions where some . For this range of k there can be just one such and can be chosen in 6 ways.

The standard adjustment procedure says that the number of such compositions (for a given ) will be: .

Thus the required solution will be: .

Finally, if (remember higher values are counted by looking at 54 - k), counting 6 compositions of k contains the possibility that two of the summands are ten or more. The counting procedure thus needs Inclusion-Exclusion to work and this will result in the answer:

.

Note: there is a more straightforward way of dealing with this part of the problem using generating functions.

Now I haven't got on to generating functions yet so I don't really want any comments with regard these.

I understand some of this. However in the solution I get lost at some points. Specifically where it mentions: 54-k and between 10 and 19. I would like explaining how they got to the second and third terms of the answer. I understand how the first term is reached. However I do not understand why you must take off and add on a second and third term. I am severely confused. I will give rep for anyone who makes it click for me (spread over several days as this is a monster read i know.)

Also I do not know why the "latex" formulas aren't red...
2. Anyone?? Any help will be much appreciated, and I will give rep (more than one days worth if necessary).
They got the same in the solution but added: Note that this is valid since all digits are bounded above by 9 which is greater than 5 From what I understand of this statement, I think that it is saying, each digit is only one digit (eg 10 is two digits, 1 and 0), so the question can be answered in this way. Is my understanding of this final statement correct??
I don't think either what you are saying, or what you are quoting is particularly well worded.

The point is that in the analysis, we are treating as non-negative integers, not digits. That is, we're not doing anything to make sure they satisfy the restriction of being one of 0, ..., 9.

But if they add up to 5, and none of them are negative, then none of them can be bigger than 5, so they certainly are <= 9, so they are digits.

I understand some of this. However in the solution I get lost at some points. Specifically where it mentions: 54-k and between 10 and 19.
The point of discussing 54-k is to stop us having to consider 30-39 and 40-49; if we know the answer for k, we know the answer for 54-k, so we don't need to consider cases above 27.

For a sum between 10 and 19, it is possible that one of our numbers is > 9 (and so we're counting a "solution" that isn't actually valid, because one of the numbers isn't a digit).

So, we count the number of solutions where one number is > 9 and subtract them from the solutions where we have no restrictions on the numbers.

I would like explaining how they got to the second and third terms of the answer. I understand how the first term is reached. However I do not understand why you must take off and add on a second and third term. I am severely confused. I will give rep for anyone who makes it click for me (spread over several days as this is a monster read i know.)
For the case 20-29, we subtract off the cases where we choose one number to be > 9; since in every "bad solution" one number is > 9, this removes all the bad solutions. But in fact, we will have 'double counted' the cases where two numbers are > 9 (e.g. all the cases where x_1> 9 and x_2>9 are counted in both the cases "x_1 > 9" and the cases "x_2 > 9"). So to allow for that we subtract back off the cases where 2 numbers are > 9.

This is standard "inclusion-exclusion" stuff; you need to get comfortable with this because it comes up all the time.
4. I do not understand why in the formula throughout the whole question that takes the form:

, k must take a value below 10??

I think this is essentially where the confusion lies, as for me, my answer would have been:

and I do not understand why you must do any inclusion or exclusion on this question to start with.

Thank you for you answer though, it has cleared up quite a few aspects.
5. I don't understand what you're saying. The whole point of the "long" answer is to give a solution for the case when k > 9. So what is "k must take a value below 10??" supposed to mean?
6. (Original post by DFranklin)
I don't understand what you're saying. The whole point of the "long" answer is to give a solution for the case when k > 9. So what is "k must take a value below 10??" supposed to mean?
Sorry I didn't make myself clear, I will rephrase.

I understand the concept of inclusion exclusion, so the second term is taking into account solutions which the first didn't, and the third is subtracting those which have been counted twice (so they are only counted once).

I understand the reason you need to do the long answer is to give a solution for when k>9.

My question is, why does the short solution not suffice as a solution for all k, greater than, and less than and equal to 9.

I realise that inclusion-exclusion MUST be used, because in part c) of the question we must look at "the case when k>9". However I don't understand WHY it must be used due to k being > 9.

Why does not suffice as an answer?

Due to inclusion-exclusion being used, must not take into account all solutions, however which solutions does it not take into account. (What does the second term take into account which the first doesn't?).

I apologise if you think you have already answered this, but I am working through it and doing my best. I am sure the penny will drop soon
7. When k = 10, includes solutions like x1=x2=...=x5=0, x6 = 10.
8. (Original post by DFranklin)
When k = 10, includes solutions like x1=x2=...=x5=0, x6 = 10.
This sentence basically made the penny drop, and me feel like an absolute arse all in one... I can't believe something so simple did not click until it was spelled out. Thank you.

I have gone through the working and come to the same answer as the solution (with many more workings than shown).

I will rep you when i can in thanks, but i tried and I can't for two weeks. (it seems I require your help far too often).
9. (Original post by DFranklin)
When k = 10, includes solutions like x1=x2=...=x5=0, x6 = 10.
Sorry, but one last question. for the values of k you want, due you choose which terms in the solution to use. for example, the second term would only make sense if so if you wanted to find the answer for k=6 would you just plug k=6 into the first term...
10. Yes.

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: July 27, 2010
Today on TSR

Not anymore!

### University open days

• University of Lincoln
Wed, 12 Dec '18
• Bournemouth University
Midwifery Open Day at Portsmouth Campus Undergraduate
Wed, 12 Dec '18
• Buckinghamshire New University
Wed, 12 Dec '18
Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams