Register to reply 
Combinatorics problem: find a number of 5 digits...by Freyja
Tags: combinatorics 
Share this thread: 
#1
Mar1512, 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∙(n1)∙(n2)∙(n3)∙…∙(nm+1) = [itex]\frac{n!}{(nm)!}[/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 5digit 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 tenthousands). If we look at the series of variations (3digit 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
Mar1512, 09:48 PM

Sci Advisor
HW Helper
Thanks
P: 25,228

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.



#3
Mar1612, 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 19841985 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 1415 year old student should have. But I'm unable to solve it from the point I left. However, thanks again. Anybody else? 


#4
Mar1612, 07:05 AM

Sci Advisor
HW Helper
Thanks
P: 26,148

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. 


#5
Mar1612, 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 


#6
Mar1612, 07:52 AM

HW Helper
Thanks
P: 5,325

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 


#7
Mar1712, 01:02 PM

P: 327

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 5digit number and s is the sum of its digits. You have already discovered that there are 60 numbers in the set of 3digit 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] 


#8
Mar1812, 08:49 PM

HW Helper
Thanks
P: 5,325

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



#9
Mar1812, 10:32 PM

Sci Advisor
HW Helper
Thanks
P: 25,228




#10
Mar1912, 05:57 AM

Sci Advisor
HW Helper
Thanks
P: 26,148

we can narrow it down …
we know that abcde = 1332*(a+b+c+d+e) = 4*9*37(a+b+c+d+e) so 9abcde so 9a+b+c+d+e (every highschooler knows that! ) and therefore 81/abcdeso 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 


#11
Mar1912, 02:07 PM

P: 5

Thanks everybody for your valuable input, it has really help me to see it more clear
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. 


#12
Mar1912, 02:24 PM

Sci Advisor
HW Helper
Thanks
P: 26,148

Hi Freyja!
and 11988 = 9*1332 … you did get 1332, didn't you? 


#13
Mar1912, 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 