Turn on thread page Beta

Awful discrete question... watch

Announcements
    • Thread Starter
    Offline

    1
    ReputationRep:
    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:  x_1+x_2+x_3+x_4+x_5+x_6=5 , x_i \geq 0

    This is found by  \displaystyle \binom{n+k-1}{n-1} where  n = 6, k = 5 \Rightarrow \displaystyle \binom{10}{5}

    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:  1+\displaystyle\sum^9_{k=1} \displaystyle \binom{k+5}{5} 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:  10 \leq k \geq 19 . Then the number of non-negative 6 compositions of k is  \binom{k+5}{k} , but some of these may have summands greater than 9.

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

    The standard adjustment procedure says that the number of such compositions (for a given i) will be:  \binom{(k+10)+6-1}{k-10} = \binom{k-5}{k-10} .

    Thus the required solution will be:  \binom{k+5}{k} - 6\binom{k-5}{k-10} .

    Finally, if  20 \leq k \geq 27 (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:

     \displaystyle \binom{k+5}{5} - 6\displaystyle \binom{k-5}{k-10} + \displaystyle \binom{6}{2}\displaystyle \binom{k-15}{k-20} .

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

    Thank you for anyone who reads through the whole thread and answers...

    Also I do not know why the "latex" formulas aren't red...
    • Thread Starter
    Offline

    1
    ReputationRep:
    Anyone?? Any help will be much appreciated, and I will give rep (more than one days worth if necessary).
    Offline

    18
    ReputationRep:
    (Original post by adie_raz)
    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 x_1, ..., x_6 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.
    • Thread Starter
    Offline

    1
    ReputationRep:
    I do not understand why in the formula throughout the whole question that takes the form:

     x_1+x_2+x_3+x_4+x_5+x_6=k , k must take a value below 10??

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

     \binom{k+5}{5} = \binom{n+k-1}{n-1} = \binom{n+k-1}{k} 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.
    Offline

    18
    ReputationRep:
    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?
    • Thread Starter
    Offline

    1
    ReputationRep:
    (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  \binom{k+5}{5} 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  \binom{k+5}{5} not suffice as an answer?

    Due to inclusion-exclusion being used,  \binom{k+5}{5} 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
    Offline

    18
    ReputationRep:
    When k = 10, \binom{k+5}{5} includes solutions like x1=x2=...=x5=0, x6 = 10.
    • Thread Starter
    Offline

    1
    ReputationRep:
    (Original post by DFranklin)
    When k = 10, \binom{k+5}{5} 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).
    :top:
    • Thread Starter
    Offline

    1
    ReputationRep:
    (Original post by DFranklin)
    When k = 10, \binom{k+5}{5} 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  k \geq 10 so if you wanted to find the answer for k=6 would you just plug k=6 into the first term...
    Offline

    18
    ReputationRep:
    Yes.
 
 
 
Reply
Submit reply
Turn on thread page Beta
Updated: July 27, 2010

University open days

  • University of Lincoln
    Brayford Campus Undergraduate
    Wed, 12 Dec '18
  • Bournemouth University
    Midwifery Open Day at Portsmouth Campus Undergraduate
    Wed, 12 Dec '18
  • Buckinghamshire New University
    All undergraduate Undergraduate
    Wed, 12 Dec '18
Poll
Do you like exams?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Equations

Best calculators for A level Maths

Tips on which model to get

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.