Return to WowDVDFilm
A few days ago, there was a ToM that presented a problem where 8 variables could be valued as single digits 0 to 9, but there could NOT be a repeating value. Such as W could not equal D. The eight variables were W,O,D,V,F,I,L, and M.
My question is how many combination would there be? Review the WOW ToM - and figure out the number of combinations are possible with this set of eight variables, and is there a trick here? If so what?
My question is how many combination would there be? Review the WOW ToM - and figure out the number of combinations are possible with this set of eight variables, and is there a trick here? If so what?
Labels: logic
posted by Ragknot at
2:44 PM
65 Comments:
Hi Ragknot. Ignoring detailed inspection (else would end up with only two possibilities).
W can range 1-9=> 9 choices, O can range 0-9 less 1 because of W => 9 choices too. D has 8 choices, V has 7, F has 6, I has 5, L has 4 amd M has 3 choices.
So total combinations = 9*9*8*7*6*5*4*3 = 9*9!/2 = 1 632 960.
Ok, but I didn't include the wow/dvd so this leaves you with the combinations, minus a way to get to two possiblities.
I understand your arithmetic, but there's something missing.
(Unless I figured it wrong :) )
This post has been removed by the author.
Oooops. D can't be 0. Now I don't tust my calculation at all. But hey, I'll suggest M has 10 choices, L has 9, I has 8, F has 7, V has 6, O has 5, D has 3, W has 2: that's purely for the purpose of calculaton the total combinations.
That gives 10*9*8*7*6*5*3*2 = 10!/4 = 14 515 200.
Is that better?
I'll bet that you got it right :)
I'm not sure I understand the question. The two answers that you gave in the earlier ToM are 212/606 and 242/303, The only "trick" that I can see to arrive at this answer is that it is equal to FILM/9999.
9999 = 3 x 3 x 11 x 101, so since DVD is a 3 digit number it must be made up from these factors or be a multiple of them.
It can't be 101 since D > W, so that leaves 303, 606 or 909.
That should narrow down the number of combinations. For what it's worth, FILM must be divisible by 11(a factor of 9999 not used in making up DVD) but I don't see how that helps.
This post has been removed by the author.
Hi WoO. A priori, why should FILM be divisible by 11, and why should DVD have a strong relationship to 9999? Of course that turns out to be the case, but I don't see it as obvious at the beginning.
Rewriting as WOW*9999=DVD*FILM, we can only say DVD is a factor of WOW*9999. It can have a factor common to WOW and a factor common to 9999.
I agree that DVD <> 101 as W >= 101, but can't see why you so quickly dismiss 33 etc. as a factor without further reasoning. If WOW had a factor 11, then DVD=121 seems OK (without other considerations).
If you keep on looking for ways to reduce the brute force combinations, you'll ultimately completely solve the problem by hand :) That's why I didn't do it that way - I think Ragknot is interested in the run-time of a quick and dirty brute force program.
WoO, please feel free to shoot me down. I may be missing something obvious:)
I've definitely lost my confidence in my combinatoric result. Have I got agreement with your calculation Ragknot?
WOW? I see there's been more post than I imagined since I left my office.
Sorry, I just wanted to say "WOW" :)
First let me say, that the W and the D have the limitatons that they can't be zero, because of the way the problem is presented. I think you got that. But the clue for that was in the "review" the original problem.
But the fact that W and D can't be zero, it affects the proportions of the other variables.
Let's look at the O. From my calculations it can be zero, 1/8 of the time, while it one thru 9.... only 7/72 of the time. (the nine 7/72 makes 7/8).
Now, Chris, do you think it is still think it approximately 1,451,520?
To the Wiz... Do you get the problem now?
P.S. I got a follow upquestion, but I have not figured an answer for it.
What are the 1/8th and 1/72nds of the time things? I'll stick with my answer unless you throw me a bone.
Just noticed you said 1451520, I'd already pulled that and upped it to 14515200.
I know, strangely I left off a zero.
Chris, you're right in theory that DVD doesn't have to be a multiple of 101. However, as you'll see from WOW x 3 x 3 x 11 x 101 = FILM x DVD, if DVD is not a multiple of 101, then FILM must be. All four digit multiples of 101 contain repeated pairs of digits, which is verboten.
So, V is 0 and D is 2 or more. All other digits can be 1-9. So, my answer to Ragnot (off the top of my head) is 8 (for D) times 8 x 7 x 6 x 5 x 4 x 3 = 161,280
I need the Deep Thought quote along the lines of "what exactly is the question?"
If we keep analysing the possibilities, then the answer is 42, ooops I mean 2 i.e. only 212/606=3498/9999 and 242/303=7986/9999 are allowed.
If it is taken as a combinatorics where of 8 variables, 2 can range from 1-9 and 6 can range from 0-9 but restricted by no 2 having the same value, then it's 14515200 (I think).
If we do partial analysis there will be many possible different answers, depending on how many constraints we find and use.
I fancy some confusion has been introduced because a small misunderstanding on the first problem. I'd noticed that Ragknot had be comparing ratios of numbers. That always worries me because rounding errors might make an equality test fail when it should pass. My hint about 9999 was because using that info the problem only needed fast integer multiplications and comparisons. I notice these things as I was a programmer for about 25 years.
WOW :) so much writing. Greetz.
... I'm also biased because Ragknot wrote a deeply nested "for loop" to brute force his way to the answer. I think that I've calculated the number of passes through the innermost loop. Ragknot, would you put a counter near the end of your innermost for loop to double-check?
... Ragknot had used a "small" parameter to deal with rounding errors.
I don't think I could "analyse" my way to the two solutions. I think I would need to resort to "brute force" fairly soon, if not immediately, after the point that I reached in my previous post. As you say, it depends on exactly what the question is, and what Ragknot means by "trick" in his posting of the question.
This post has been removed by the author.
Despite posting the original problem, I didn't actually work through it, so I'm only assuming that brute force isn't required.
I only posted it because ToM seemed to have fallen asleep. I didn't work through it as I already knew the answer (from the source site).
Let's look at a small part first. Suppose we look at W and O. What are the number of combinations? 81 right? Now one more step, what about W, O, and D? Combinations for these? 576. Can you see that?
(I have to leave fow work now)
Hi Ragknot. W and O gives 9*(10-1) = 81, no problem there. D has 9-2=7 possibilities => 567 (so I guess you made a typo). V has 10-3=7, F has 6, I has 5, L has 4 and M has 3. So have 9*9*7*7*6*5*4*3=1 428 840. LOL yet another answer.
I think I see what I'm doing wrong. I'm not using conditionals. It's 0 (zero) that's mucking me up.
Although I'm posting this, I'll carry on on a scrap of paper.
I realise that I really don't know what the question is and I'm not sure how to handle that W and D can't be 0. But that isn't an extra constraint if 0 has been used up elsewhere. So result depends on the order in which you choose to select the variables (or something like that).
What do you get if you put the counter in the innermost loop for the program you actually wrote?
I can safely say that I'm well and truly baffled by this one.
First lets agree that W and D have extra constraints. They can't be zero. I don't see how the order could matter. But it might help to get to the answer quicker.
1. W has nine posssibilities.
2. O would have 10 possibilities, but it can't be the same as W, so it also has nine possibilites. Then WO pair gives 81 combinations.
3. Next look at D. It can't be zero, it can't be whatever W is, and it can't be what O is. Now just concentrate on O and D. If O is zero, then D has 9 possibilities, but if O is not zero, the D has only 8 possibilites.
Then include W. If O is zero, then D has eight possibilities, if O is not zero, then D and 7 possibilities.
Wow, Does that throw the combination formulas in the trash!
Not really, but it does add a curve.
Edit
Then include W. If O is zero, then D has eight possibilities, if O is not zero, then D has 7 possibilities.
I should read my post before I click "publish"
Ragknot, as far as I'm concerned, you've published a very worthwhile and challenging problem, even if you weren't fully aware of how difficult it was (assuming it is, doh!!!!)
I've got to disappear for a few hours as my Mum is in hospital.
I was aware of the difficulty, but the difficulty is not hard if you can see the path.
Let's review, we have eight variables, six of which can range from 0 to 9. Two variables can range from 1 to 9. Usually in combinations you can figure 9*8*7... with each number reduced by one. That does not work with the limitations of some variables having a different number of values.
Let's change the order to help
see the problem quicker.
Let's choose and O, then W and D
There are 10 possibilities for O.
The possibilities for each of W and D can include 1 to 9 if and only if O is zero. If O is not zero, then the opportunities for W is reduced by one. Whatever W's possibilities, D is one less.
This is not the complete answer, I am just shining a lighr on the path.
This post has been removed by the author.
Hi Ragknot. I was serious when I said "exactly what is the question?"
The answer is very code sensitive. In principle, 6 variables range 0-9 and 2 range 1-9, so that's potentially, 2^9*6^10 = 30 958 682 112 combinations. What happens next depends on where you exit you for loops. If you test for previous use of a digit early, you may say that doesn't count as a combination, but if you defer until the innermost loop, you might choose to call that a combination. I would, if I was thinking about program execution time.
I originally thought that it was going to be more like the usual combinatoric ones - it isn't. We've got a bag with 10 balls (labelled 0-9), we have to pull 8 out, but toss the 0 back if we are drawing for W or D. The probabilty of drawing 0 is a function of the order in which we are choosing the number for. i.e. do we draw for FILM first or last?
It's an extra good problem because it involves working out what the problem actually is.
September 17, 2009 4:46 PM
.. or something like that ;)
The question is this...
1. Eight variables
2. Each has to be a unique value and within a spcific range.
3. Two have a range from 1 to 9
4. Six have a range from 0 to 9.
How many combinations of these specs are possible?
For simplicity use the variables
W,O,D,V,F,I,L, and M and set W and D with the 1 to 9 range.
This is what I deduced from the beginning. Do you see how W and D can't be zero? It's obvious in the fraction. Do you see how if one of the six is not zero, it changes the possibilities for W and D?
If not inspect just W and O and see what are the combinations if O is zero and what if it is not zero.
It is not difficult, but it maybe impossible if you follow some preconcived logic.
Hi Ragknot. I think that I've now more or less got my head around it.
The result is affected by the order you assign the digits to the letters - there is no single correct answer. The problem has to state the order in which the assignments are to be made. At least, I'm pretty sure that's at least a necessary condition if you want a unique answer.
Another approach, which I'm too lazy to take, is too get a statistical expectation value, based on averaging over many possible random assignment experiments. i.e. randomly choose a digit and randomly choose a letter to assign it to. Obviously you'd use statistical arguments and do it on the back of a very large envelope. It's smacks of Bayesian probability stuff.
Just to help get you a nice big comment count - do you count drawing a 0 and a W or D as a combination? I guess probably not. But in a computer program, you might still use up a for loop. I keep mentioning the computer as I suspect that's, at least partly, what led you to post the problem.
No, W or D being zero, is NOT or has it ever been possibility.
I found the number of combinations then sought to understand how that could be. Along the way I found a possibility of 7 in 72.
I mentioned that in an early post and I assumed you disreguarded it.
Here's a test. It seems that maybe you have a mental block.
Use the variables O, W and D.
Assume O equals one, write down the combinations that W and D could make if O is one. You should find exactly 58.
Now assumee O is zero, write down and count the combinations for w and D. You will find 72.
Hey, we could make a fortune with a gambling game using this insight.
Everyone who thought they knew how to figure odds would be taken in.
Oh, and to go one more step, Let O be 0 to 9 and see if you can find the combinations for all three. Maybe you learn where the 576 comes in?
I think I've got it!
If draw 0 then for each possible letter of OVFILM then get (for each, using O for example), get (1*9*8*7*6*5)*(4*3) = 9!/2combinations (and it doesn't matter about what order you do the rest as you only get anagrams of the above). As there are 6 acceptable letters get 6 times that = 3*9!
If don't draw 0 at all, then get 9*8*7*6*5*4*3*2 = 9! combinations.
So altogether get 4*9! = 1 451 520 combinations (that's a strangely familiar number). That's my last try ... unless^^
I have some confidence (barring silly mistakes) that that is the number you've been looking for. So all my previous posts were based on a hidden preconception - as you suggested. Despite trying to present evidence to the contrary, my guts told me that there has got to be a definite number. Please tell me that you agree with my revised answer. I've read it half a dozen times before hitting Publish. I reckon you should now see why I avoid combinatoric questions, they can get out of (my) hand too easily. With hindsight, that's how I should have done it in the first place. Rambling mode off.
Hi Ragknot. A bunch of your posts came through while I was writing my masterpiece.
I hadn't ignored the 72 thing - I actually asked you where they came from.
I know W and D can't be zero, but try telling that to a (computer generated) bag initially containing all 10 digits that has no idea you're trying to pick a number to assign to W or D. The point is only relevant to how many times a for loop is called.
This post has been removed by the author.
Guess what, although I'm sure I'm on the right track, I think I may still not be doing the non-0 counting quite right. I can't promise that I'll look again tonight, it's just gone 4 am here.
PS I've just become sure that I'm not counting right. I'll be back in half an hour (or less).
My last PS was due to a mental abberation - I think I am counting right after all.
LOL. Why can't W or D be 0? The problem doesn't say they have to be 3 digit numbers ^^
Clearly W or D being 0 won't satisfy the equation. But there again, there are only 2 possible combinations that do actually satisfy the equation. Either we analyse the equation and determine constraints, or we don't. The only reasonable "constraint" is that you can't use the same digit twice - but that's OK as it is part of the problem definition and not based on a analysis.
So my final final answer is 10^8 = 100 000 000 combinations - seriously ;)
... and thank you again for the problem. It made a voyage to self-discovery. I'm amazed at how long it's taken me to state the obvious. LOL.
LOL yet again. I meant 10!/2 = 1 814 400, not 10^8.
Chris,
Your mental block wins again.
There are 576 combinations for the WOD (three variables). I have list them and counted them here.
http://ragknot.blogspot.com/
You could show that I am wrong by finding just one more that's not on the list.
1,451,520 is the correct answer to the number of combinations for the eight variables. In the beginning you gave this times 10, and I batted it back to you corrected.
Then I was suprised when you computed it, but before I could answer, you changed your mind about it.
The part that reveals the solution is just understanding how the first three give 576 combinations. Then the other 5 variables are just the same the O in the first 3.
The count of O's in WOD reveal the strange result in this ToM.
O Count Of O's
--------------
0....... 72
1....... 56
2....... 56
3....... 56
4....... 56
5....... 56
6....... 56
7....... 56
8....... 56
9....... 56
Hi Ragknot. Thanks for the table. I checked through the first few hundred entries, and am taking the rest on trust as you've obviously got it right and I can see it corresponds to 9*8*8 = 576 which makes a sort of sense.
Part of my block is, even though I know there are 10 digits, I keep on saying/using 9 for a normal letter, and 8 for W and D. So more of an extremely persistent senior moment.
I'll try again in a moment. I hope that the penny drops for me soon. Meanwhile, you haven't commented on the fact that you are treating W and D as special cases. I will do so again as you have spent time and trouble with that in mind - and it does make it more fun (did I really say that?) :) Greetz
The 14 515 200 was an double error. I'd actually calculated 10! * 4 instead of 10!/4 = 907 200 (which is the wrong answer as well).
OK. It look like my SEPT 17 7:56PM post is correct. (It's the only one I had any confidence in - all the previous ones kept on nagging at me as being wrong). It also cunningly avoids the explicit 576 sub-combinations. I had suspected that the bounced back 1 451 520 was a clue rather than a typo - I weakly hinted at that when I (finally reproduced it.
Using the same logic (as my only good post) on WOD, I get:
If draw 0 then 9*1*8 combinations. If don't draw 0 then get 9*8*7 combinations. Adding => 9*8*8 =576 combinations (praise the lord). Are we done? :)
I'll think 20 times before I dare do another combinatorics question ;)
W and D can not be zero because the
equation WOW/DVD would not be written as WOW/DVD if either W or D was zero.
The values of W and D are evenly distributed. Each value, 1 to 9 occurs 1/9 of the time.
However, the values of the other six variables are not evenly distributed. For each of these variables, the zero value occurs 1/8 of the time and the values of 1 to 9 occur 7/72 of the time.
Although 4*9! = 1,451,520 gives the correct number of combinations, I can't figure out how that it relates to this problem.
This post has been removed by the author.
Hi Ragknot, It seems I've got the upper hand(s) at last (enormous grin of smugness).
First: WOW/DVD. Normally the problem would explicitly state that WOW and DVD are 3 digit numbers - but nowhere has this ever been stated in the problems - you (and I until last few posts) have just taken it for granted. So I assert that there's nothing wrong with e.g. 070/121=FILM/9999. That give FILM approx 5834 (yes, I'm cheating big time:)) or 121/090 (OK that gives FILM > 9999, but now I'm analysing). As I've said before, if you keep on analysing, in principle, you'll end up with only 2 allowed combinations.
Second: I don't really have a response :) except examine the method again. With hindsight, it was the most obvious way to tackle it. It wasn't luck that I got the 576 either.
I'll admit, I made a real hash of it to start with, but am now sure that I've finally got to grips with it. Greetz.
As I hadn't been clear about the case when that W and D can be 0, then I get 10*9*8*7*6*5*4*3 = 10!/2. I skipped tha detail as I had erroneously written 10^8, which seemed to be self-explanatory. 10!/2 isn't so obvious.
I didn't originally tackle the WOD sub-problem (in my masterpiece) as I just went for the whole problem in one go.
Wow, almost 60 comments!
Hi Ragknot, you seem to have got a jackpot with your problem. If I was smarter you wouldn't have done so well though ;)
I'm burning my brain out on the Warren Buffett one now - I'm finding that one very fiddly, having a hard time making any equations for it. Beginning to think brute force would help.
Didn't you mean "WOW, almost 60 comments!"
There you go, you've now got 60 comments :)
This post has been removed by the author.
Ragknot. In my "masterpiece" it was important to not go (10*9*8*7*6*5)*(4*3) when drawing because that would still give W or D a chance of being 0. So I considered separately what happens if you drew 0 for O, 0 for V etc.
The template I used was(OVFILM)*(WD). The order in OVFILM was uninmportant, only the definite assignment of 0 to each of OVFILM mattered. i.e I was breaking it down into 6 mini-problems.
Not sure if that makes it clearer or muddier.
Hi Ragknot, I'm tidying up loose ends again. Having determined that that there are 576 OWD combinations, that leaves VFILM with 7*6*5*4*3 = 7!/2 combinations. Put those together => 1 451 520 combinations (again).
Mental or what. Easier still is there are 9*8 combinations of WD and 8*7*6*5*4*3 = 8!/2 combinations of OVFILM. Put those together = 1 451 520 altogether. Grrr - now that really is what I should have done over 60 posts ago. I had definitely lost the plot, very big time.
OMG. Guess what, I almost did it right in the very first post, I just made an incredibly silly mistake. LOL.
Post a Comment
Links to this post:
Create a Link
<< Home