Combinatorics problem: find a number of 5 digits...


by Freyja
Tags: combinatorics
Freyja
Freyja is offline
#1
Mar15-12, 08:38 PM
P: 5
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


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?
Phys.Org News Partner Science news on Phys.org
NASA's space station Robonaut finally getting legs
Free the seed: OSSI nurtures growing plants without patent barriers
Going nuts? Turkey looks to pistachios to heat new eco-city
Dick
Dick is offline
#2
Mar15-12, 09:48 PM
Sci Advisor
HW Helper
Thanks
P: 25,170
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.
Freyja
Freyja is offline
#3
Mar16-12, 06:25 AM
P: 5
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?

tiny-tim
tiny-tim is offline
#4
Mar16-12, 07:05 AM
Sci Advisor
HW Helper
Thanks
tiny-tim's Avatar
P: 26,167

Combinatorics problem: find a number of 5 digits...


Hi Freyja! Welcome to PF!

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.
Freyja
Freyja is offline
#5
Mar16-12, 07:41 AM
P: 5
Hi Tim, thanks for answering!

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) 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
NascentOxygen
NascentOxygen is offline
#6
Mar16-12, 07:52 AM
HW Helper
P: 4,715
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

awkward
awkward is offline
#7
Mar17-12, 01:02 PM
P: 325
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]
NascentOxygen
NascentOxygen is offline
#8
Mar18-12, 08:49 PM
HW Helper
P: 4,715
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).
Dick
Dick is offline
#9
Mar18-12, 10:32 PM
Sci Advisor
HW Helper
Thanks
P: 25,170
Quote Quote by NascentOxygen View Post
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).
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):

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
tiny-tim
tiny-tim is offline
#10
Mar19-12, 05:57 AM
Sci Advisor
HW Helper
Thanks
tiny-tim's Avatar
P: 26,167
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! )
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
47952 -> 36 ? no
71928 -> 54 ? no
83916 -> 63 ? no
Freyja
Freyja is offline
#11
Mar19-12, 02:07 PM
P: 5
Thanks everybody for your valuable input, it has really help me to see it more clear


Quote Quote by tiny-tim View Post
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! )
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
47952 -> 36 ? no
71928 -> 54 ? no
83916 -> 63 ? no
Mr. Tim, you are officially my hero

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.
tiny-tim
tiny-tim is offline
#12
Mar19-12, 02:24 PM
Sci Advisor
HW Helper
Thanks
tiny-tim's Avatar
P: 26,167
Hi Freyja!
Quote Quote by Freyja View Post
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.
one 9 was from 1332, and the other was from the "9" relation between abcde and a+b+c+d+e

and 11988 = 9*1332
you did get 1332, didn't you?
Freyja
Freyja is offline
#13
Mar19-12, 02:36 PM
P: 5
Ahhhh, the divisibility by 9 rule, alright. Sorry about my brain fart

And yes, I got up to 1332.

I owe you one


Register to reply

Related Discussions
Number theory: Find the last three digits Calculus & Beyond Homework 3
Combinatorics: Choosing Sets of Distinct Digits Calculus & Beyond Homework 1
combinatorics problem regarding number of possible paths General Math 1
combinatorics problem about determining number of paths Calculus & Beyond Homework 0
Number of digits in n! Programming & Computer Science 8