aff@duke.UUCP (Amr F. Fahmy) (04/08/85)
I am a new subscriber to net.puzzle and I don't know if the following puzzle appeared before, if it did please accept my appologies. Given 12 identical items all weighing the same but only one is "different" in weight from all the others. You are given a balance (no weights), a pen (just in case you need to mark items) and nothing else to use. You are asked to identify the different item using the balance the least number of times. This puzzle has always appealed to me very much, I don't know if there is a systematic way of solving it, I would be interested in case such a solution exists. Amr F. Fahmy CSNet : aff@duke Distribution: net.puzzle
mercury@ut-ngp.UUCP (Larry E. Baker) (04/10/85)
[.] > Given 12 identical items all weighing the same but only one is "different" in > weight from all the others. You are given a balance (no weights), a pen > (just in case you need to mark items) and nothing else to use. You are asked > to identify the different item using the balance the least number of times. Look in Horowitz & Sahani's "Data Structures" for an excellent description of using decision trees to solve this sort of problem. I don't remember exactly how the solution went, but it went something like: Divide the pile into two halves. Weigh them against each other. One will weigh more. Now halve the two piles, and weigh the halves against each other. One pair will weigh exactly the same; this is now your reference pair. You can repeat this process (there may be subtitlties not expanded on here, but it's late in the afternoon, and I have an EE Class in 15 minutes...) but you can repeat this process, eventually coming up with two items that do not weigh the same. Select an item from the reference pair and check each item. The one that weighs the same as the item from the refrence pile is NOT the different one. Note: There may be an easier way to do this (I think there is -- I have very little faith in my memory) but the above technique should work. -- - Larry Baker @ The University of Texas at Austin - ... {seismo!ut-sally | decvax!allegra | tektronix!ihnp4}!ut-ngp!mercury - ... mercury@ut-ngp.ARPA
wca@ut-ngp.UUCP (William C. Anderson) (04/10/85)
>Given 12 identical items all weighing the same but only one is "different" in >weight from all the others. You are given a balance (no weights), a pen >(just in case you need to mark items) and nothing else to use. You are asked >to identify the different item using the balance the least number of times. > Amr F. Fahmy I don't know if this is the optimum solution, but this problem can be solved in 4 weighings. Method: 1 - Divide 12 objects into 3 piles of 4 objects each. Label piles A, B, and C. 2 - Compare A and B. ( 1st weighing ) 3 - Compare A and C. ( 2nd weighing ) At this point, you now know which pile is "different", and whether the difference is "heavier" or "lighter". For the sake of brevity, assume pile C is "different". Then step 2 implies that A is a "reference" pile, and step 3 will determine whether C is heavier or lighter. 4 - Divide C ( the "different" pile ) into halves and compare to find the "different" half. ( 3rd weighing ) 5 - Take the "different" half, divide into halves ( in this case, unit objects ) and compare. This test determines the "different" object. ( 4th weighing ) I suspect that this problem has already been hashed over in net.puzzle, but I don't recall seeing it. Is there a way to solve this in 3 or *fewer* weighings? William Anderson "Do you have a lifestyle yet?" - Zippy the Pinhead
muffy@lll-crg.ARPA (Muffy Barkocy) (04/10/85)
In article <5702@duke.UUCP> aff@duke.UUCP (Amr F. Fahmy) writes: >I am a new subscriber to net.puzzle and I don't know if the following >puzzle appeared before, if it did please accept my appologies. > >Given 12 identical items all weighing the same but only one is "different" in >weight from all the others. You are given a balance (no weights), a pen >(just in case you need to mark items) and nothing else to use. You are asked >to identify the different item using the balance the least number of times. > >This puzzle has always appealed to me very much, I don't know if there is >a systematic way of solving it, I would be interested in case such a >solution exists. > > Amr F. Fahmy > >CSNet : aff@duke >Distribution: net.puzzle This was the first problem we did in my algorithms class this semester. The solution can be found in COMBINATORIAL ALGORITHMS by Edward M. Reingold, Jurg Nievergelt and Narsingh Deo, beginning on p. 14. I will post it, if that is desired. Muffy
kvetter@dartvax.UUCP (Keith Vetter) (04/10/85)
> I am a new subscriber to net.puzzle and I don't know if the following > puzzle appeared before, if it did please accept my appologies. > > Given 12 identical items all weighing the same but only one is "different" in > weight from all the others. You are given a balance (no weights), a pen > (just in case you need to mark items) and nothing else to use. You are asked > to identify the different item using the balance the least number of times. *** REPLACE THIS LINE WITH YOUR MESSAGE *** The problem is commonly stated with 12 coins one of which is counterfeit and has the wrong weight. There are two ways to solve this problem: 1) use the results of earlier weighings to determine which coins to weigh next. 2) use a set of independent weighings with the coins in such a way to cover all possibilities. After finishing the weighings, the results are combined to yield the coin. The second method can be generalized to more than 12 coins but is not very appealing (at least to me). The first method has many cases to keep track of and is as follows: We'll use the suffix l, h to denote being light or heavy. 1) Weigh coins 1-4 against 5-8. if they balance then 9-12 contain the bad coin 2) weigh coins 9, 10 against 11, 1 (a good coin) if they balance then 12 is bad 3) weigh 12 against 1 to see if 12 is heavy or light. else we have either 9L, 10L, 11H or 9H, 10H, 11L 3) weigh 9 against 10 if they balance 11 is bad else with 2) we know which is bad. if the first weighing doesn't balance then assume the pan with coins 1-4 went up (the other case is identical so we'll just solve this case). Now we know that one of these is true 1L 2L 3L 4L 5H 6H 7H 8H. 2) weigh 1L, 2L, 5H against 3L, 6H, 9 (good coin) if it balances then either 4L, 7H or 8H so 3) weigh 7H against 8H if they balance then #4 is bad else the heavy one is bad. if 2) had the 1, 2, 5 side go down then either 5H or 3L 3) weigh 5H against 9 (good coin) if 2) had the 1, 2, 5 side go up then either 1L, 2L or 6H. 3) weigh 1L against 2L if they balance then #6 is bad else the light one is bad. So for 12 coins it takes 12 weighings and you can tell which coin is bad and whether it's heavy or light. Keith Vetter Dartmouth College
gjk@talcott.UUCP (Greg Kuperberg) (04/10/85)
> Given 12 identical items all weighing the same but only one is "different" in > weight from all the others. You are given a balance (no weights), a pen > (just in case you need to mark items) and nothing else to use. You are asked > to identify the different item using the balance the least number of times. > > Amr F. Fahmy It's pretty obvious that you can't do this problem in two weighings; I won't go through the tedium of demonstrating it. However, there is a way to do it in three, yes *three* weighings. Here's how: 1. Divide the weights into three piles of four. Weigh the one group of four against another. If they are equal, go to step 6. If they are unequal, proceed to step 2. 2. I'll call one pile the heavy pile, the other the light pile, and the third the neutral pile. Take three weights from the heavy pile and one from the light pile and weigh them against the fourth heavy weight and three neutral weights. If the side with three neutrals is heavier, go to step 3. If the two sides are equal, go to step 4. If the side with three heavies is heavier, go to step 5. 3. At this point there are two possibilities: Either the single "light" weight is the different one, or the single heavy weight on the side of the three neutrals is the different one. Weigh the light one against any neutral. If it is the same weight, then the single heavy weight is the different one. If it is lighter, then of course it is the different one. We can stop and report which weight is different. 4. In this situation, we know that the oddball weight is one of the three lights which was not involved in the second weighing. Weigh one of these against the other. If they are equal, the third is the oddball; if they are different, the lighter one is the oddball. We can stop here. 5. Here we know that the different weight is one of the three heavies that were on the same side in the second weighing. Weigh one of these against the other. If they are equal, the remaining heavy is the oddball; if they are different, the heavier one is the oddball. We can stop and report which weight is not identical to the others. 6. In this step, we know the oddball is among the four weights not used in step 1. Call the other eight weights "safe" and call these four "suspicious". Take two suspicious weights and weigh them against two safe ones. If the scales balance, throw away these two suspicious weights and keep the ones you didn't weigh; if the scales don't balance, throw away the two you didn't weight and keep the two you did weigh. Either way, go to step 7. 7. You are left with two suspicious weights and many safe weights. Weigh one suspicious one agianst the safe one; if the scales balance, the suspicious weight which was weighed is the one you're looking for, otherwise the suspicious weight which you didn't weigh is the one you want. -- Greg Kuperberg harvard!talcott!gjk "The eerily accurate drawing of Goetz showed the face of the 'before' figure in comic-book ads for body-building devices."-Time Magazine, April 8
ken@osiris.UUCP (Ken Harkness) (04/10/85)
> I am a new subscriber to net.puzzle and I don't know if the following > puzzle appeared before, if it did please accept my appologies. > > Given 12 identical items all weighing the same but only one is "different" in > weight from all the others. You are given a balance (no weights), a pen > (just in case you need to mark items) and nothing else to use. You are asked > to identify the different item using the balance the least number of times. > > This puzzle has always appealed to me very much, I don't know if there is > a systematic way of solving it, I would be interested in case such a > solution exists. > > Amr F. Fahmy > > CSNet : aff@duke > Distribution: net.puzzle The problem is solvable in a maximum of 4 uses of the balance, assuming that you can put at least half of the weights on one side of the balance. The solution is as follows: (1) Put 6 on one side, 6 on the other. One side will weigh more than the other. As of yet, we do not know whether the "different" one weighs more or less. (2) Take the 6 on the heavier side, and balnace 3 of these against the other 3. If the balance is equal, then the "different" weight is in the other set of 6, and the different weight is lighter than the other weights. If the balance is tilted, then the "different weight is one of the 3 on the heavier side, and is heavier than the other individual weights. In the latter case, the problem is solved in only 3 tries. (3) [only if (2) was equal]. Balance 3 of the other set of 6 vs its complement. Now take the 3 on the lighter side. (4) With 3 weights (A,B,C) left, and knowledge of whether it is heavier or lighter, simply balance A vs B and if (a) they balance, C is the "different" one, (b) they don't balance, and you know it should be heavier, or (c) they don't balance, and you know it should be lighter, choose the appropriate weight. Ken Harkness
ronbe@tekred.UUCP (Little Guy) (04/10/85)
-> Given 12 identical items all weighing the same but only -> one is "different" in weight from all the others. You -> are given a balance (no weights), a pen (just in case you -> need to mark items) and nothing else to use. You are asked -> to identify the different item using the balance the least -> number of times. The puzzle is easy if you know that the odd object is heavier or lighter than the others. The odd one can be found in three weighings consistently. Just divide the group in thirds, and put two of the thirds on the balance. If it balances, you've eliminated all objects on the balance. If not, you've eliminated the other third and (providing you know that the odd one is heavier), one of the groups that are on the balance. The same three weighings can be used to find the heavy object in 27. Things get a little trickier when one doesn't know that the odd object is heavier or lighter. I'd still take the same approach. Weigh 1/3 against 1/3. If the scale balances, you've eliminated 2/3 of the objects. If not, you've eliminated 1/3. This method could be used recursively with large numbers of objects. The last check would be with the odd object (and possibly one other) against one (or two) eliminated (equal) objects to determine if the left-over object was heavy or light. At worse, you will eliminate int(x/3) objects each time. (x is the number of un- eliminated objects left. At worst, this will take 7 weighings: (e=eliminated -even- object) 1) 4 - 4 eliminates at least 4 (8 left) 2) 2 - 2 eliminates at least 2 (6 left) 3) 2 - 2 eliminates at least 2 (4 left) 4) 1 - 1 eliminates at least 1 (3 left) 5) 1 - 1 eliminates at least 1 (2 left) 6) 1 - e eliminates 1 (1 left) 7) 1 - e determines heavy/light At best, it could take 3 weighings: 1) 4 - 4 eliminates at most 8 (4 left) 2) 1 - 1 eliminates at most 2 (2 left) 3) 1 - e could determine heavy/light Perhaps a better puzzle would be to find the probability of finding the odd object in 3, 4, 5, 6, or 7 weighings. Send those replies! -- Support bacteria - It's the only culture some people have! ...tektronix!tekred!ronbe (Ron Bemis)
kvetter@dartvax.UUCP (Keith Vetter) (04/11/85)
> So for 12 coins it takes 12 weighings and you can tell which coin > is bad and whether it's heavy or light. Oops wwhat I meant to write was "So for 12 coins it takes 3 weighings...." Keith Vetter Dartmouth College
nader@hound.UUCP (N.MEHRAVARI) (04/11/85)
>Given a pan balance and 12 pool balls of which one may be either too >light or too heavy, determine with uses of the balance which >ball, if any, is faulty and whether it is too light or too heavy. It can be done in three weighings: Label the coins 1,2,3,.....12, and make the following three weighings: 1) 1,2,3,4 against 5,6,7,8 2) 1,2,3,5 against 4,9,10,11 3) 1,6,9,12 against 2,5,7,10 Let L,S,and H stand for "is lighter than", "is the same as," and "is heavier than," respectively. The the folling table determines the false coin, if any, and its nature. outcome of the three weighings the false coin ______________________________ ______________ LLL 1 is light LLH 2 is light LLS 3 is light LHS 4 is light HLH 5 is light HSL 6 is light HSH 7 is light HSS 8 is light SHL 9 is light SHH 10 is light SHS 11 is light SSL 12 is light HHH 1 is heavy HHL 2 is heavy HHS 3 is heavy HLS 4 is heavy LHL 5 is heavy LSH 6 is heavy LSL 7 is heavy LSS 8 is heavy SLH 9 is heavy SLL 10 is heavy SLS 11 is heavy SSH 12 is heavy SSS all good
steve@siemens.UUCP (04/11/85)
You couldn't be more wrong!! (insert the sound of a gong here) Taking 1/3 vs 1/3 in the first weighing is right, but after that you messed up! Consider that there are 24 possible cases (12 coins * heavy or light), and three weighings can discriminate 3^3 = 27 cases. That means that one might possibly be clever enough to distinguish which of 13 coins is heavy or light in only 3 weighings, and we really ought to try hard to find a way for 12. In the first weighing we must divide the 24 cases into three groups each of not more than 9 cases. 1/3 vs 1/3 divides into three sets of 8 cases each. Now cleverly find ways of weighing coins to divide each of those sets of 8 into sets of no more than 3 each -- I won't bother to say how because someone else already posted a solution (which is not unique). To prove you cannot distinguish which one is heavy or light from 13 coins, in three weighings. The first weighing must split the 26 cases into three sets of no more than 9 cases each. It must be a weighing of n coins against n coins, and will divide the 26 cases into 2n, 26-2n, and 2n cases for outcomes of <, =, and > respectively. For no integral value of n is 2n <= 9 and 26-2n <= 9. Therefore there is no way to determine which of 13 coins is heavy or light in 3 weighings. In fact, by just looking at the first weighing you can show by a generalization of the proof above that for w weighings, an upper bound on the number of coins you can distinguish is (3^w - 3)/2 (which is an integer), and the first weighing must be 1/3 vs 1/3 of those coins, which is also integral. Can you actually find the bad coin (and whether it is heavy or light) from 39 coins in 4 weighings? Steve Clark ...princeton!siemens!steve
bruce@bnr-vpa.UUCP (Bruce Townsend) (04/12/85)
Grab this line, bug...
Ron Bemis seems to claim that it can take up to 7 weighings to
isolate the odd object (and tell whether it's light or heavy)
from a group of 12 otherwise identical objects.
In fact, it can *always* be done in three! I have the solution
if anyone is interested, but the major hint is:
SPOILER***
Note that three weighings of 4 against 4 (and 4 aside)
have a total of 27 outcomes for the experiment. (Each weighing
has 3 outcomes- tip left, tip right, or balance, and 3x3x3 = 27)
You only need 24 possibilities (one of 12 is either light or heavy)
so label objects 1-12, and discover 3 groupings that will yield
a unique result for each possibility.
--
-Bruce Townsend
Voice Processing Applications,
Bell-Northern Research,
Ottawa, Ontario.
Mail path: {utzoo, utcs, bnr-di, bnr-mtl}!bnr-vpa!bruceholmes@dalcs.UUCP (Ray Holmes) (04/12/85)
Actually, the problem as stated can be solved in the same number of weighings if there are 13 objects. Yes the process of solving it is systematic. Ray