#31
|
|||
|
|||
Re: Much much tougher brain teaser
this is a trivial problem.
Do you see why? Indy |
#32
|
|||
|
|||
Re: Much much tougher brain teaser
[ QUOTE ]
-Matt [/ QUOTE ] Thanks for the photo. It almost makes up for the hour I lost working that one out and trying to put it into words! -ptmusic |
#33
|
|||
|
|||
Re: Much much tougher brain teaser
Why do I always have to try and cheat? Even when you are holding a .357 mag to my head. I just got what little brains I have blown out. [img]/images/graemlins/frown.gif[/img]
I had fun trying though, nice job ptmusic. [img]/images/graemlins/laugh.gif[/img] Vezzini: Haha.. you fool! You fell victim to one of the classic blunders. The most famous is: Never get involved in a land war in Asia. Only slightly less well know is this: Never go in against a Sicilian when death is on the line! |
#34
|
|||
|
|||
Re: Much much tougher brain teaser
[ QUOTE ]
Vezzini: Haha.. you fool! You fell victim to one of the classic blunders. The most famous is: Never get involved in a land war in Asia. Only slightly less well know is this: Never go in against a Sicilian when death is on the line! [/ QUOTE ] best movie ever |
#35
|
|||
|
|||
Re: Much much tougher brain teaser
I came across this elegant solution here.
Of 12 coins, one is counterfeit and weighs either more or less than the other coins. Using an old-fashioned balance with two scales, and performing only three measurements, you have to find out which coin is counterfeit, and whether it is lighter or heavier then the other coins. How would you do that? The basic idea of this solution is to perform the three measurements, look at the result of each measurement, and then look at the way each coin has participated in the measurements to identify the only coin that could have caused this particular combination of results. For instance, if the three results are: equal (0), right side heavier (R), left side heavier (L), or, in short, 0RL, then it must have been the coin that was not in the first measurement, on the right in the second measurement, on the left in the third measurement, and that coin is heavier than the others, or (mirrored) the coin that was not in the first measurement, on the left in the second measurement, on the right in the third measurement, and that coin is lighter than the others. Note how the measurement result 0RL and the participation of a heavier coin in the measurements coincide. So all we have to do is to distribute the 12 coins over the scales of the three measurements in such a way that no coin participates in the three measurements in the same way (or mirrored) as any other coin. The distribution below is one of many possible distributions that fulfills this requirement: 1, 2, 7, 10 against 3, 4, 6, 9 1, 3, 8, 11 against 2, 5, 6, 7 2, 3, 9, 12 against 1, 4, 5, 8 If the measurements result in 0RL, then it can be seen from this distribution that coin 8 is lighter than the other coins. No other coin can explain the outcome 0RL. DONE. We have thus found a solution to the problem. But how can such a solution be found? I.e., how can a distribution of coins over the measurements such as the one above be found? And why should there be four coins on each side of the balance in each measurement? The answer is in the list of logical steps below. Each measurement has three possible results: equal (0), right side heavier (R), or left side heavier (L). The three measurements together can therefore have a total of 3x3x3 = 27 different outcomes, namely any possible combination of 3 letters out of 0, L, and R, i.e., 000, 00L, 00R, 0L0, 0LL, 0LR, .... , RRL, RRR. We are looking to find the right one among 24 different statements, i.e., "coin 1 is heavier", "coin 1 is lighter", ... , "coin 12 is lighter". We need to map each statement to an outcome, so that if that outcome occurs, the statement to which it maps must be true. Part of such a mapping table could be: LR0 means "coin 1 is heavier" RLR means "coin 2 is heavier" etc. This mapping table serves two purposes. It identifies the counterfeit coin and its weight after having performed the measurements, but it also tells us where to put each coin in each measurement. For instance, since we want LR0 to mean "coin 1 is heavier," coin 1 must participate in measurement 1 on the left side, in measurement 2 on the right, and not at all in measurement 3. Outcome 000 is useless to us since it means that the counterfeit coin was never part of a measurement and we can not tell whether it was lighter or heavier than the others. This leaves 26 possible outcomes that must be mapped to 24 statements. If LR0 means "coin 1 is heavier," then RL0 (its mirror outcome) must mean the opposite, i.e., "coin 1 is lighter." This is so because mapping LR0 to "coin 1 is heavier" determines where coin 1 occurs in the three measurements, and if that coin is lighter instead, the measurements will result in the mirror outcome. We can therefore group the 26 outcomes into 13 pairs (each outcome with its mirror outcome). The table can now be reduced to mapping 12 statements about coins being heavier to 12 outcomes (each outcome taken from a different pair). We have one pair of outcomes too many. If we make a list of all outcomes, and count the numbers of L's and R's (not counting 0's) that appear in the first position of each of the outcome strings, we will end up with the number 9 (or 18 when including mirror outcomes). This means that 9 coins would participate in the first measurement. Counting L's and R's in the second and third position would also yield 9. Since we can not distribute 9 coins evenly over 2 scales, the pair of outcomes we are not going to use should have an L or R in each position, such as LLL and its mirror outcome, RRR. Not using that pair will leave 8 coins in each measurement. Alternatively, any other pair of outcomes with three letters, e.g., (LRR, RLL), can be dropped from the outcomes and a correct distribution can still be found using the remaining 12 outcome pairs. We are now left with 12 outcome pairs and 12 statements about each coin being heavier. Since the numbering of the coins is irrelevant, the only remaining choice we have is which outcome of each pair we will use in the table. If we now start to map "heavier" statements to outcomes arbitrarily, we run the risk of ending up with 6 coins on the left and 2 coins on the right in a measurement, which isn't going to tell us much. We must ensure that in each measurement (position in the outcome string), there are as many coins on the left (symbols L) as there are on the right (symbols R). We can achieve this by taking a mirror outcome if the scales get out of balance. The rest is a bit of rather straightforward trial and error. Let's decide not to use the pair (LLL, RRR). From each remaining pair, we pick one outcome in such a way that we have the same number of L's and R's in each position of the string. We save the pairs of outcomes with two 0's to the end to make it easier to get the scales back into balance. LLR \ LRL > 3 letters, one of which is different RLL / we now have two L's in each column against one R, so let's use some more R's R0R \ 0RR > one 0 and twice the same letter RR0 / each column has now one R too many LR0 \ 0LR > one 0 and two different letters R0L / we still have one R too many in each column L00 \ 0L0 > two 0's and one letter 00L / Since we now have an equal number of L's and R's in each of the three columns of the outcomes (namely 4), we have an equal number of coins on each side of the scales in each measurement. To complete the table, we only need to write down the "heavier" statements next to the outcomes (and the "lighter" statement to the corresponding mirror outcomes). The numbering of the coins is of course irrelevant: LLR "coin 1 is heavier" RRL "coin 1 is lighter" LRL "coin 2 is heavier" RLR "coin 2 is lighter" RLL "coin 3 is heavier" LRR "coin 3 is lighter" R0R "coin 4 is heavier" L0L "coin 4 is lighter" 0RR "coin 5 is heavier" 0LL "coin 5 is lighter" RR0 "coin 6 is heavier" LL0 "coin 6 is lighter" LR0 "coin 7 is heavier" RL0 "coin 7 is lighter" 0LR "coin 8 is heavier" 0RL "coin 8 is lighter" R0L "coin 9 is heavier" L0R "coin 9 is lighter" L00 "coin 10 is heavier" R00 "coin 10 is lighter" 0L0 "coin 11 is heavier" 0R0 "coin 11 is lighter" 00L "coin 12 is heavier" 00R "coin 12 is lighter" As explained before, the left part of the table tells us exactly where each coin participates in each measurement. The resulting distribution of coins over scales is the one given at the beginning. In addition, the table above can be used to find the counterfeit coin after having performed the three measurements. |
#36
|
|||
|
|||
Re: Much much tougher brain teaser
This is not really elegant. It is effective, but it is a ton of work and writing, etc. Not elegant at all. A more elegant solution that I came up with is to weigh 4 against 4. If it doesn't balance, move three normal ones (which weren't involved in the first weighing) to the heavy side, three from the heavy side to the light side and three from the light side off. Now weigh again.
If the heavy side is still heavy, then either the one heavy left on it is heavy or the one light on the light side is light. Weigh the light one against a normal and if it is light, it is that one that is weird and it is light. If they balance, then the heavy one from the heavy side is the weird one and it is heavy. If the heavy side from the first weighing is now light on the second weighing, then you know that one of the three heavy ones that you moved to the original light side must be heavy. So weigh one against one and if it is unbalanced it is the heavy one and it is heavy. If it is balanced, the one you didnt weigh is weird and it is heavy. If the second weighing balances, then one of the three light ones that you took off is light. Repeat the three heavies procedure to find the light one. If the initial weighing balanced, then you know that it is one of the four that you didn't weigh that is weird. For the second weighing, weigh three of those against three normal ones. If the weird side is heavy, repeat the heavy procedure from above to determine which one it is and it is heavy. If the weird side is light, same procedure to determine which one and it is light. If they balance, then the one you didn't weigh at all yet is weird. Weigh it against a normal one to see if it is light or heavy. QED. |
#37
|
|||
|
|||
Re: Much much tougher brain teaser
Elegant meaning the weighings are all the same, regardless of the outcome of the previous weighings.
I am still reading it, but your solution seems to be exactly the one a guy i work with just handed me. (This problem has essentially ceased all work in the engineering department of my company for the past day). *Edit* Yup, exactly the same. I wish he explained his as clearly as you did, it took me forever to decipher 3 pages of notes. |
#38
|
|||
|
|||
Re: Much much tougher brain teaser
[ QUOTE ]
Elegant meaning the weighings are all the same, regardless of the outcome of the previous weighings. [/ QUOTE ] OK, I can buy that. Seems more 'brute force' than 'elegant' to me, but matter it's just semantics. [ QUOTE ] (This problem has essentially ceased all work in the engineering department of my company for the past day). [/ QUOTE ] Good to know why we're lagging behind the Japanese. [ QUOTE ] I wish he explained his as clearly as you did, it took me forever to decipher 3 pages of notes. [/ QUOTE ] Just because the solution is elegant doesn't mean the explanation is, unfortunately. |
|
|