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

Freyja

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?

Dick

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

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

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

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

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

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

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

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

tiny-tim

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

Thanks everybody for your valuable input, it has really help me to see it more clear


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

Hi Freyja! 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

Ahhhh, the divisibility by 9 rule, alright. Sorry about my brain fart

And yes, I got up to 1332.

I owe you one