1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics problem: find a number of 5 digits

  1. Mar 15, 2012 #1
    Hi everybody, I would really appreciate some help with the following problem. First of all I want to apologize for my poor English, I hope to be able to translate everything clearly. Thanks in advance.

    1. The problem statement, all variables and given/known data

    Find a number of 5 different digits that equals the sum of all numbers of 3 digits that can be made with said 5 digits.


    2. Relevant equations

    V[itex]^{m}_{n}[/itex] = n∙(n-1)∙(n-2)∙(n-3)∙…∙(n-m+1) = [itex]\frac{n!}{(n-m)!}[/itex]

    I'll clarify that the above expression means "Variations without repetition of m elements taken from a set of n elements". I know in English you guys don't use the term "variation" as we do here in Spain for this particular context; said variations are the "ordered" combinations (so to speak) of m elements from a set of n elements, and obviously result of the product of "disordered" combinations for the permutations of m. I hope that makes it clear :smile:


    3. The attempt at a solution

    So the number we're looking for will have the form abcde (there's no repetition of digits, since the problem states that they're all different) and it'll equal the sum of all the possible variations of 3 elements that can be done with the digits {a,b,c,d,e}

    Such variations are 60 (according to the formula, V[itex]^{3}_{5}[/itex] = 5∙4∙3 = 60), as follows:

    abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde,
    acb, adb, aeb, adc, aec, aed, bdc, bec, bed, ced,
    bac, bad, bae, cad, cae, dae, cbd, cbe, dbe, dce,
    cab, dab, eab, dac, eac, ead, dbc, ebc, ebd, ecd,
    bca, bda, bea, cda, cea, dea, cdb, ceb, deb, dec,
    cba, dba, eba, dca, eca, eda, dcb, ecb, edb, edc.

    Now let's calculate the sum of all the above numbers, which we know will be a 5-digit number that I'll call XMhtu (u be the column of the units, t that of the tens, h the hundreds, M the thousands and X the ten-thousands).

    If we look at the series of variations (3-digit numbers) above, we can see that every last number of them (the numbers in the units column) is repeated as many times as variations of 2 digits can be formed with the other four digits of the number we're trying to find (V[itex]^{2}_{4}[/itex] = 4∙3 = 12), so every number is repeated 12 times. Therefore, the sum of all the numbers in the column of the units (u) will be:

    Ʃu = 12a + 12b + 12c + 12d + 12e = 12(a+b+c+d+e)

    and the same reasoning applies to the other columns; of course, the numerical value of the column of the tens will be the same as that of the units multiplied by 10 and the numerical value of the column of the hundreds will be that of the units multiplied by 100:

    Ʃt = 10 ∙ Ʃu = 120(a+b+c+d+e)

    Ʃh = 100 ∙ Ʃu = 1200(a+b+c+d+e)

    And that's as far as I got. Now, how do I relate the number XMhtu to the number abcde that's been asked?
     
  2. jcsd
  3. Mar 15, 2012 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Well, abcde=10000*a+b*1000+c*100+d*10+e, right? That should be equal to your XMhtu. I hope this a computer problem. I don't see any clever way to solve it by hand.
     
  4. Mar 16, 2012 #3
    Thanks for your answer Dick. However, no, it shouldn't be a computer problem, given the fact that this problem is from my old high school book (first year at that, I do not know the equivalent grade in American schools, but I was 14 at the time). So we're talking about the 1984-1985 scholastic year. We didn't even have computers at that time!

    That's why it's driving me nuts, it's supposed to be a simple problem to be resolved with a very simple intuitive approach and the "knowledge" that a 14-15 year old student should have. But I'm unable to solve it from the point I left.

    However, thanks again.

    Anybody else?
     
  5. Mar 16, 2012 #4

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Welcome to PF!

    Hi Freyja! Welcome to PF! :smile:

    Suppose the number is abcde.

    How many numbers will there be of the form a** ?

    How many *a*?

    How many **a?

    Add them all up, with the *s as 0s.

    Then do the same for b c d and e. :wink:
     
  6. Mar 16, 2012 #5
    Hi Tim, thanks for answering! :smile:

    I have already calculated the amount of numbers, they're 60 as I stated above. That's not my issue.

    My issue is, which are those numbers? How do I find their values?

    I mean, I know already how many numbers and their forms, but which ones are they?

    In other words, which number would be a, which would be b, which would be c, and d, and e?

    Please don't laugh at me guys (or do it, lol) :tongue: I know this is probably the easiest part of the problem, I just cannot grasp it. I got stuck and I don't see an algebraic way to solve it.

    Thanks again :redface:
     
  7. Mar 16, 2012 #6

    NascentOxygen

    User Avatar

    Staff: Mentor

    There's no neat analytic solution that I know of.

    You are solving 1332(a+b+c+d+e) = 10000*a+b*1000+c*100+d*10+e

    8668a - 332b - 1232c - 1322d - 1331e = 0

    Case: a=1.
    this would form at most a 4 digit number. Not possible.

    Case: a=2, so this would make our number less than 17336
    Consider b=1, this leaves - 1232c - 1322d - 1331e = -17004
    with {c,d,e} ∈ N so b=1 is feasible
    Trying c=3, ...

    continue https://www.physicsforums.com/images/icons/icon2.gif [Broken]

    :smile:
     
    Last edited by a moderator: May 5, 2017
  8. Mar 17, 2012 #7
    I am not very good at this kind of problem (and have not solved it), but here is an observation that may help. Let's say x is the 5-digit number and s is the sum of its digits. You have already discovered that there are 60 numbers in the set of 3-digit numbers extracted from x. So visualize the column of numbers adding up to x; each of the digits of x must appear exactly 60/5 = 12 times in the 1s column, 12 times in the 10s column, and 12 times in the 100s column. So

    x = 100 (12s) + 10(12s) + 1(12s) = 1332 s

    [edit] Oops, never mind, I see this has already been noted above, essentially. [/edit]
     
  9. Mar 18, 2012 #8

    NascentOxygen

    User Avatar

    Staff: Mentor

    I was hoping someone would persist with this, to find the solution. It would be a good exercise for a spreadsheet. I'd manually set the cell values for 'a' and 'b' and let the spreadsheet try to find integer solutions for the other variables (just because I like to retain some control over what's happening, otherwise I feel redundant to the solution). :smile:
     
  10. Mar 18, 2012 #9

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I wouldn't use a spreadsheet. I'd use a programming language. There aren't that many 5 digit numbers. Here's a python version (I've never done code here, so I'm just guessing on the formatting):

    Code (Text):

    for a in range(10):
      for b in range(10):
        for c in range(10):
          for d in range(10):
            for e in range(10):
              if (1332*(a+b+c+d+e)==a+10*b+100*c+1000*d+10000*e):
                print e,d,c,b,a
     
     
    Last edited: Mar 18, 2012
  11. Mar 19, 2012 #10

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    we can narrow it down …

    we know that abcde = 1332*(a+b+c+d+e) = 4*9*37(a+b+c+d+e)

    so 9|abcde

    so 9|a+b+c+d+e (every high-schooler knows that! :biggrin:)

    and therefore 81/abcde

    so abcde is a multiple of 11988

    abcde = 11988*k where k < 9 and a+b+c+d+e = 9k

    so (ignoring repeats) it must be one of …
    23976 -> 18 ? no
    35964 -> 27 ? yes :wink:
    47952 -> 36 ? no
    71928 -> 54 ? no
    83916 -> 63 ? no
     
  12. Mar 19, 2012 #11
    Thanks everybody for your valuable input, it has really help me to see it more clear :smile:


    Mr. Tim, you are officially my hero :surprised

    However, where do 81 and 11988 come from? I can see 9 is a divisor of the number that's being asked, but I don't see where did you get 81 and 11988.
     
  13. Mar 19, 2012 #12

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi Freyja! :smile:
    one 9 was from 1332, and the other was from the "9" relation between abcde and a+b+c+d+e :smile:

    and 11988 = 9*1332 …

    you did get 1332, didn't you?​
     
  14. Mar 19, 2012 #13
    Ahhhh, the divisibility by 9 rule, alright. Sorry about my brain fart :blushing:

    And yes, I got up to 1332.

    I owe you one :biggrin:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Combinatorics problem: find a number of 5 digits
  1. Digit 5 repetition (Replies: 3)

  2. Combinatorics problem (Replies: 2)

Loading...