Reply
Wed 26 Jul, 2006 08:30 pm
You're at the deli buying loaves of bread as you ate all of them for dinner last night. You asked for 20 loaves of bread but the shopkeeper gave you a poisoned one hidden in the 19 real ones. The poisoned one looks and feels exactly the same as the real ones, except for a slight difference in weight. You were warned by the honest townspeople about this deli and they told you a way to find out which loaf of bread is poisoned by using a balancing scale. However, you do not know whether the poisoned loaf of bread is heavier or lighter than the real ones.
Find the poisoned loaf in 4 moves using the scales (meaning you're only allowed to place the loaves of bread on the balancing scale 4 times). The poison can't be traced in any way.
I know of three ways this works out without forcing the shopkeeper to tell you by means of hitting him in the head with the scale.
Try to get them all.
Weigh AAAAAA and BBBBBB with CCCCCCCC on the side.
If it doesn't balance, then let's say the As are heavier than the Bs. Weigh the As against six of the Cs to determine if an A is heavy or a B is light. Let's say an A is heavy. We now have two more weighings to determine which of six loaves is heavy.
Weigh A1A2 and A3A4 with A5A6 on the side.
If it balances, either A5 or A6 is heavy. Weigh them against each other to determine which is heavier and has the poison.
If it doesn't balance, then split the heavy side up and weigh them against each other to determine which is heavier and has the poison.
If it balances, then the poison is in the Cs. Weigh the Cs against eight of the As and Bs to determine if a C is heavy or light. Let's say a C is heavy. We now have two more weighings to determine which of eight loaves is heavy.
Weigh C1C2C3 and C4C5C6 with C7C8 on the side.
If it balances, either C7 or C8 is heavy. Weigh them against each other to determine which is heavier and has the poison.
If it doesn't balance, let's say C1C2C3 is heavier. Weigh C1 and C2 with C3 on the side. If they balance C3 has the poison. Otherwise, the heavier one has the poison.
markr wrote:Weigh AAAAAA and BBBBBB with CCCCCCCC on the side. 1st weighing
If it doesn't balance, then let's say the As are heavier than the Bs. Weigh the As 2nd weighing against six of the Cs to determine if an A is heavy or a B is light. Let's say an A is heavy. We now have two more weighings to determine which of six loaves is heavy.
Weigh A1A2 3rd weighing and A3A4 with A5A6 on the side.
If it balances, either A5 or A6 is heavy. Weigh 4th weighing them against each other to determine which is heavier and has the poison.
If it doesn't balance, then split the heavy side up and weigh them against each other to determine which is heavier and has the poison. It says that you don't know if the poisoned one is heavier or lighter than the other ones
If it balances, then the poison is in the Cs. Weigh the Cs against eight of the As and Bs to determine if a C is heavy or light. Let's say a C is heavy. We now have two more weighings to determine which of eight loaves is heavy.
Weigh C1C2C3 and C4C5C6 with C7C8 on the side.
If it balances, either C7 or C8 is heavy. Weigh them against each other to determine which is heavier and has the poison.
If it doesn't balance, let's say C1C2C3 is heavier. Weigh C1 and C2 with C3 on the side. If they balance C3 has the poison. Otherwise, the heavier one has the poison.
sry wrong. that was a nice try and i thought it was right at first. i had to read over it several times to catch that.
What you didn't catch is my statement that an A is heavy (versus a B being light). The same method applies if a B is light.
Here's another way of solving the problem--one that doesn't require branching. (Branching = if ____ then ____ ) Instead, you do everything at once and just read the results to determine which loaf is bad.
Using letters to identify loaves:
Weighing #1
Left Side / Right Side - Off the Scale
A B C D E F G / H J K L M N P - R T U V W X
Weighing #2
Left Side / Right Side - Off the Scale
A B C K L M W / D E F N P R X - G H J T U V
Weighing #3
Left Side / Right Side - Off the Scale
A D G K N T W / B E H L P U X - C F J M R V
Weighing #4
Left Side / Right Side - Off the Scale
A D G H J V W / B C F K M R U - E L N P T X
(someone should check that I coppied all those correctly '
')
Now, if after performing the four trials, you get the result LLER (L = left side tilts down, etc) then I know that loaf C is heavy; RREL = loaf C is light; LLRR = B is heavy; and so on. Each loaf has a unique solution. Notice that each loaf actually has a set of answers, depending on whether it is heavy or light. These two answers are mirror images of each other. One outcome, EEEE, has no mirror image.
Given that each weighing has three possible outcomes (Left, Right, or Even), there are 3^4 = 81 total possible outcomes to the four trials. However, since EEEE doesn't have a match, it cannot help up determine whether the loaf is heavy or light. (In this problem, it doesn't really matter if the poison makes the loaf heavy or not--you just have to identify which one not to eat.) Thus, we will throw out that possibility. Also, since each loaf needs two outcomes--one if it's heavy and the other if it's light--we reduce the total possible loaves we could solve: (4^3 - 1) / 2 = 40 Therefore, we could conceivably buy 40 loaves and still identify which one is bad with only four weighings! (Actually, it may not be quite 40 since the restriction that the number on the left side and right side have to match--that is an additional constraint that can reduce the number of solutions. The 12-coin problem which is the same but with 12 coins and only three weighings cannot be expanded to 13 despite (3^3 - 1) / 2 = 13)
markr i was confused by the last statement where you said that the heavier one would be the one with the poison what if the heavier one was actually normal and the lighter one was poisoned
redav im gonna have to read yours alot to understand it a little bit better
its not how i did it but it might work idk
ok let me figure this out would this still work if i said this
Weighing #1
Left Side / Right Side - Off the Scale left
A B C D E F G / H J K L M N P - R T U V W X
Weighing #2
Left Side / Right Side - Off the Scale right
A B C K L M W / D E F N P R X - G H J T U V
Weighing #3
Left Side / Right Side - Off the Scale left
A D G K N T W / B E H L P U X - C F J M R V
Weighing #4
Left Side / Right Side - Off the Scale
A D G H J V W / B C F K M R U - E L N P T X even
i just noticed u skipped letters which might have thrown me off let me recheck
rafiki282 wrote:
i just noticed u skipped letters which might have thrown me off let me recheck
When I do these sort of things, I skip "I," "O," "Q," and "S," because they are too similar to 1, 0, and 5, which can really screw things up.
rafiki282 wrote:markr i was confused by the last statement where you said that the heavier one would be the one with the poison what if the heavier one was actually normal and the lighter one was poisoned
If the heavy assumption is false, substitute light for heavy in the remaining steps.
if it was lighter than the other loaves but you didnt know that. how would you know if the poison was in the heavier one or the lighter one.
you might have just worded it wrong but it sounds like your saying the heavy one is the one with the poison when it very well could be the light one.
yes but if you substituded the heavy for the light you still wouldnt know if the poison was heavier or lighter
like i said you dont no if the poisoned one is heavier or lighter than the others
You know after the second weighing because you're weighing a group with the poisoned loaf against a group of normal loaves.
The 36-loaf Problem
Okay, same problem, but now you have 36 loaves to sort through instead of 20. (This is the maximum that 4 weighings can determine).
I have not constructed a simultaneous solution like for the 20 loaves yet, but here is a branching method.
Method:
These sort of problems can be viewed as systems of equations like in algebra. You must have at least as many equations as variables; otherwise, the problem is indeterminate, which means you will not be able to solve the problem for _all_ possibilities.
The results or outcomes of the trials (Left, Right, or Even) are the equations since that is what gives you information about your variables. In this problem there are up to 3^4 = 81 equations.
The variables are the possibilities, such as the first loaf is heavy (1H), the first loaf is light (1L), the second loaf is heavy (2H), etc. In this problem there are 36*2 = 72 variables. Since 81 > 72, we are in good shape.
When using a branching technique, you are effectively consuming your equations with each trial. Therefore, after each weighing, you must still always have fewer variables than equations. So after the first weighing, you have only 3^3 = 27 equations remaining. As for the variables, all the possibilities that would contradict your observed outcome of each trial are eliminated, and never have to be worried about again. For example, if the first weighing shows that loaf #3 cannot be heavy (3H is no longer a possible solution), then you do not have to worry about 3H in any subsequent weighings.
Let's look at an example: You have 12 loaves & 3 weighings. That means the possibilities are 1H, 1L, 2H, 2L, ... 12H, 12L = 24 total. You place loaves 1-5 on the left side and 6-10 on the right, with 11-12 left off. The remaining possibilities for each outcome are:
Left: 1H, 2H, 3H, 4H, 5H, 6L, 7L, 8L, 9L, 10L
Right: 1L, 2L, 3L, 4L, 5L, 6H, 7H, 8H, 9H, 10H
Even: 11H, 11L, 12H, 12L
Note that all possibilities are placed into one of the three branches. However, since we just used up one of our weighings, we only have 2 left so the number of outcomes is now 3^2 = 9 for each branch. If you got lucky and the first weighing was balanced, then you would still be in good shape, but if not, you now have 10 possibilities, and 10 > 9; thus, you can no longer solve that branch.
You can construct an assortment of different variations of this problem using the above technique--for example, what if 2 of the loaves were poisoned? How many could you have and still be able to find them with only 4 weighings?
Solution (spoilers):
Weighing I
Place loaves 1-12 on the left, 13-24 on the right, and 13-36 off the scale. If it balances, it is identical to the famous 12-coin problem, (24 possibilities < 27 outcomes, check!) which I assume you already know, so I won't discuss it. (If you don't, it can be solved just like this problem.) If it doesn't balance, then you have one of twelve loaves that could be heavy plus one of twelve that could be light = 24 possibilities < 27 outcomes, check!
Weighing II
I will call the potential heavies H and the potential lights L. (I realizes this changes notation in the middle of the problem, sorry.) Place the first four Hs with the first four Ls on the left. Place the second four Hs and the second four Ls on the right. The third set of Hs and Ls are left off. Outcomes:
Left: First four Hs are heavy + second four Ls are light = 8 < 9, check!
Right: Second four Hs are heavy + first four Ls are light = 8 < 9, check!
Even: Third four Hs are heavy, third four Ls are light = 8 < 9, check!
Weighing III
No matter how the second weighing went, you now have four loaves that may be heavy and four that may be light. Place the first two Hs with the first L on the left. Place the third H, the second L, and one loaf that has been completely eliminated from consideration (thus we know it is neither heavy nor light) on the right.
Outcomes:
Left: First two Hs are heavy + second L is light = 3 < or = 3, check!
Right: Third H is heavy + first L is light = 2 < 3, check!
Even: Fourth H is heavy + last two Ls are light = 3 < or = 3, check!
Weighing IV
If you have two Hs + one L, weigh the two Hs against each other. If they balance, the L is light. If they don't balance, the one that drops is heavy. Problem solved.
If you have two Ls + one H, weigh the two Ls against each other. If they balance, the H is heavy. If they don't balance, the one that goes up is light. Problem solved.
If you have one H and one L, weigh the H against a loaf already eliminated (and so is known to be good). If it drops, it's heavy. If it doesn't the L is light. Problem solved.
The site that I provide a link to says 39 is possible with four weighings. It also provides a deterministic method for constructing what you call a simultaneous solution.
markr wrote:The site that I provide a link to says 39 is possible with four weighings. It also provides a deterministic method for constructing what you call a simultaneous solution.
Yes, with a simultaneous method you can actually handle 39. But with a branching method, the max is 36. This is due to the way information is collected and used. Branching methods are less efficient due to the fact that information gathered must be used immediately. If you have extra 'capacity'--e.g., on the last step I listed above, there are scenarios with only two possibilities in the last step--it cannot be used to 'go back' to a prior trial. That unused capacity is what leads to the inefficiency.
I find it interesting that four weighings is the point where this inefficiency first appears. You could give a 3-coin & 2-weighing problem followed by a 12-coin & 3-weighing problem, fully (and correctly) expecting the solver to devise branching solutions. You can then progress on to the 39-coin & 4-weighing which will stop him dead in his tracks. (That's just plain nasty.
)
The Gardner method in that website does work; however, it must have been written on-the-fly, because it is actually a very poor description (I will not say explanation, since it does not "explain" what is happening) of the process. Notice that it does not mention how to construct trials #2 and beyond--you have to infer how to do it by how the information is gathered. Unfortunately, that causes it to be confusing and many people will not get out of it anything more than a plug-and-chug algorithm.
Stumble It!
Tweet This
Bookmark on Delicious
Share on Facebook
Share on MySpace