| Blogs > Byo |
|
Byo
Canada207 Posts
You are given 12 identical coins, and one weight scale. The weight scale is only able to identify if side A is heavier or lighter than side B. You are able to put any number of coins on either side. Among the 12 identical coins is 1 fake coin, whose weight is different but whither it is heavier or not is unknown. The task is to use the scale the least number of times to determine which coin is fake. You will probably have to name the coins A-L for clarity.  | ||
|
vAltyR
United States581 Posts
Should be seven times. Weigh two coins at a time, so that's six times. One of those will produce an imbalance. Take one of the coins from the imbalanced result and weigh it against a different coin. If there is an imbalance again, that's the fake coin. If it's balanced, the other coin from the imbalance is the fake. | ||
TheYango
United States47024 Posts
Put 6 coins on each side of the scale. One side will be lighter, and one will be heavier. Take all the coins off, and put 3 on each side from the set of 6 coins that were on the lighter side. If the piles weigh the same, then the fake is heavier than normal. If they're different, then the fake is lighter than normal. If the fake is lighter than normal, take the lighter of the 2 piles you just weighed. Compare any 2 of those 3 on the scale. If they weigh the same, the third one is the fake. If they're different, the lighter one is the fake. If you found out the fake is heavier than normal, then split the heavier pile from the original weighing into piles of 3 and compare them. Take the heavier of the 2, and weigh any 2 of those 3. If they weigh the same, the third one is the fake. If they're different, the heavier one is the fake. Thats three weighings if the fake is lighter than normal, and four if the fake is heavier than normal. | ||
|
Dave[9]
United States2365 Posts
So at most it will take 7 times. | ||
|
SpiritoftheTunA
United States20903 Posts
ABCDEF vs GHIJKL (1) one will turn up heavier, say its the abc group ABC vs DEF (2) if one doesn't turn up heavier, then weigh other set GHI vs JKL (3) one of these will turn up lighter, J v A (4) K v A (5) L v A (6) EDIT strikeout part was stupid but yeah up until then i had theyango's method | ||
|
vAltyR
United States581 Posts
On April 24 2009 09:08 TheYango wrote: + Show Spoiler + Put 6 coins on each side of the scale. One side will be lighter, and one will be heavier. Take all the coins off, and put 3 on each side from the set of 6 coins that were on the lighter side. If the piles weigh the same, then the fake is heavier than normal. If they're different, then the fake is lighter than normal. If the fake is lighter than normal, take the lighter of the 2 piles you just weighed. Compare any 2 of those 3 on the scale. If they weigh the same, the third one is the fake. If they're different, the lighter one is the fake. If you found out the fake is heavier than normal, then split the heavier pile from the original weighing into piles of 3 and compare them. Take the heavier of the 2, and weigh any 2 of those 3. If they weigh the same, the third one is the fake. If they're different, the heavier one is the fake. Thats three weighings if the fake is lighter than normal, and four if the fake is heavier than normal. Ouch. Owned. >_<; On April 24 2009 09:11 SpiritoftheTunA wrote: + Show Spoiler + ABCDEF vs GHIJKL (1) one will turn up heavier, say its the abc group ABC vs DEF (2) if one doesn't turn up heavier, then weigh other set GHI vs JKL (3) one of these will turn up lighter, weigh each of them 1 by 1 against a coin from the ABCDEF set, whichever turns up lighter is correct J v A (4) K v A (5) L v A (6) max by this method is 6 + Show Spoiler + Actually, max is 4. Read TheYango's post to find out why. | ||
|
FirstProbe
1206 Posts
If both sets weigh the same, then repeat the process. This will leave you with one set of coins weighing more than the other. Take one of those sets in which there is a discrepancy, and weigh it against another set. If it weighs the same, then the other set is the one with the fake coin. If they do not weight the same, then the fake coin is in the set that you have re-tested. Following that, take the 3 coins that weighed in lighter, and weigh one against another. You'll either have your answer there, or have concluded that the coin not weighed is the lightest. This should take you 4 attempts. edit: or 3 attempts if you are more fortunate. | ||
|
Byo
Canada207 Posts
| ||
|
goldrush
Canada709 Posts
Split it up into two groups of six. Weight it. One group will be heavier than the other. (A-F) (G-L) (#1) Take one group of six. Split it into two groups of three. If they are identical weight, then use the other group of six for the next step. If they are not of identical weight, then use this group for the next step. (#2) Say that (A-C) (D-F) are of identical weight, and (G-I) and (J-L) are not. Weight (G-I) against (A-C). (#3) If they are equal weight, then use the group (J-L) for the next step. If not, then use the group (G-I) for the next step. Choose two random coins (say G and H if G-I was used from the previous step) from that group and weigh them from each other. (#4) If they are equal, then the one that remains (I) is the odd one out. If not, then weigh one of them (say, G) against coin A. (#5) If they are equal, then the other one (H) is the odd one out. If they are not, then G is the odd one out. Steps 4-5 can probably be optimized though. =/ | ||
|
Deleted User 31060
3788 Posts
If IJ is different than AB, compare A with I. If same, the coin is J (if different, coin is I) If ABCD is different with EFGH, compare ABCD with IJKL. If ABCD and IJKL are the same, compare AB with EF. If same, compare A with G. If same, the coin is H (if different, coin is G) If EF is different than AB, compare A with E. If same, the coin is F (if different, coin is E) If ABCD and IJKL are different, compare AB with EF. If same, compare A with E. If same, the coin is B (if different, coin is A) If EF is different than AB, compare C with E. If same, the coin is D (if different, coin is C) I think that takes care of all possibilities in 4 tries | ||
|
Bebop Berserker
United States246 Posts
On April 24 2009 09:08 TheYango wrote: + Show Spoiler + Put 6 coins on each side of the scale. One side will be lighter, and one will be heavier. Take all the coins off, and put 3 on each side from the set of 6 coins that were on the lighter side. If the piles weigh the same, then the fake is heavier than normal. If they're different, then the fake is lighter than normal. If the fake is lighter than normal, take the lighter of the 2 piles you just weighed. Compare any 2 of those 3 on the scale. If they weigh the same, the third one is the fake. If they're different, the lighter one is the fake. If you found out the fake is heavier than normal, then split the heavier pile from the original weighing into piles of 3 and compare them. Take the heavier of the 2, and weigh any 2 of those 3. If they weigh the same, the third one is the fake. If they're different, the heavier one is the fake. Thats three weighings if the fake is lighter than normal, and four if the fake is heavier than normal. Nice. Mine came out to be four/four but this seems right. I was just being stupid.(go figure) | ||
|
TheYango
United States47024 Posts
On April 24 2009 09:15 Byo wrote: actually, optimum method can find the result in 3 weighs regardless of heavier or lighter.... How about this: + Show Spoiler + Coins A-L. Weigh ABCD v EFGH and ABCD v IJKL. If ABCD is the same as either, the other 4 contain the fake and you know if the fake is lighter/heavier by whether that pile is lighter/heavier (e.g. if ABCD = EFGH and ABCD > IJKL, then IJKL has the fake and the fake is lighter). If ABCD is different, then ABCD contains the fake, and you know if the fake is lighter/heaver by whether ABCD is lighter/heaver than the other two. Call the pile with the fake now PQRS. Weigh PQ v RS, choose the one you know has the fake from whether the fake is heavier/lighter as determined above, and weigh those. The fake is lighter/heavier as determined above. 3 weighs every time. EDIT: wow, I can't count. Will figure out in a bit. | ||
|
SpiritoftheTunA
United States20903 Posts
On April 24 2009 09:22 TheYango wrote: How about this: + Show Spoiler + Coins A-L. Weigh ABCD v EFGH and ABCD v IJKL. If ABCD is the same as either, the other 4 contain the fake and you know if the fake is lighter/heavier by whether that pile is lighter/heavier (e.g. if ABCD = EFGH and ABCD > IJKL, then IJKL has the fake and the fake is lighter). If ABCD is different, then ABCD contains the fake, and you know if the fake is lighter/heaver by whether ABCD is lighter/heaver than the other two. Call the pile with the fake now PQRS. Weigh PQ v RS, choose the one you know has the fake from the fake weight determined above, and weigh those. The fake is lighter/heavier as determined above. 3 weighs every time. i count 4 man | ||
|
TheYango
United States47024 Posts
Wow I'm dumb. Edit in a bit. | ||
|
SpiritoftheTunA
United States20903 Posts
| ||
|
goldrush
Canada709 Posts
+ Show Spoiler + (ABCDEF) versus (GHIJKL) (ABCGHI) versus (DEFJKL) Find which group of three is heavier or lighter. Take two from the group of three, measure. If equal, odd one out. If not equal, you know whether the odd one is supposed to be lighter/heavier and that one is it. edit: nope, nvm | ||
|
TheYango
United States47024 Posts
On April 24 2009 09:29 goldrush wrote: Second try, I think I got it. + Show Spoiler + (ABCDEF) versus (GHIJKL) (ABCGHI) versus (DEFJKL) Find which group of three is heavier or lighter. Take two from the group of three, measure. If equal, odd one out. If not equal, you know whether the odd one is supposed to be lighter/heavier and that one is it. edit: or not Yeah, your first 2 weighings don't guarantee finding which group is heavier. | ||
|
OmgIRok
Taiwan2699 Posts
1a) weigh 5 coins on each scale, if there is an imbalance, then move on to step 2a 1b) same as 1a except they both weigh the same 2b) weigh the remaining 2 coins 2a) keep taking out 1 coin from both piles until the weight is the same, 3) weigh the 2 coins that you took out from the pile before it made it even weight | ||
|
TheYango
United States47024 Posts
On April 24 2009 09:33 OmgIRok wrote: 3) weigh the 2 coins that you took out from the pile before it made it even weight How does this determine the fake? None of your previous steps ascertain whether the fake is lighter or heavier. Edit: However, weighing one of those two with a third coin does. Still iffy on whether taking coins out constitutes a separate weighing, but this at least works. | ||
|
SpiritoftheTunA
United States20903 Posts
On April 24 2009 09:33 OmgIRok wrote: 1a) weigh 5 coins on each scale, if there is an imbalance, then move on to step 2a 1b) same as 1a except they both weigh the same 2b) weigh the remaining 2 coins 2a) keep taking out 1 coin from both piles until the weight is the same, 3) weigh the 2 coins that you took out from the pile before it made it even weight yeah the existence of 2a means you can't guarantee < 3 try again mang | ||
|
goldrush
Canada709 Posts
(ABGH versus CDIJ) This time, look at the pairs? ex: ABCDEF is heavier, ABGH is heavier. Then the odd one out is one of AB, measure. DAMNIT there are always the lighter-lighter options which increases the number of required weighs, doesn't work. | ||
|
KwarK
United States42864 Posts
On April 24 2009 09:33 OmgIRok wrote: 1a) weigh 5 coins on each scale, if there is an imbalance, then move on to step 2a 1b) same as 1a except they both weigh the same 2b) weigh the remaining 2 coins 2a) keep taking out 1 coin from both piles until the weight is the same, 3) weigh the 2 coins that you took out from the pile before it made it even weight 2b tells you one coin is heavier than the other. Which is the fake? | ||
|
SpiritoftheTunA
United States20903 Posts
On April 24 2009 09:37 goldrush wrote: (ABCDEF) versus (GHIJKL) (ABGH versus CDIJ) This time, look at the pairs? ex: ABCDEF is heavier, ABGH is heavier. Then the odd one out is one of AB, measure. in your example, J could be lighter and could be the fake | ||
|
Tyxiquale
Australia424 Posts
1. Weigh 3 balls against 3 balls. If they are the same, move to 2a, if they are different, 2b. You now have the information of 6 balls that are normal. 2a) You take 3 balls from one end off the scale, and grab 3 "unidentified" balls from your other pile, and weigh them. If different to 3 normal balls, then it must be in that group of 3. If they are the same, then the mystery ball must be in the final 3 balls. MOST IMPORTANTLY - you know whether the ball is heavier or lighter. 2b) You take 3 of these balls and weigh it against 3 identified balls. If they are the same, the mystery ball must be in the other 3 balls that you weighed in your first go. If not, they are in the pile you just measured. AND you know whether the ball is heavier or lighter. 3. Regardless of which method you have taken, you have now identified 3 balls, of which 1 of them is the mystery ball. AND most importantly, the information of whether it is heavier or lighter. As such, the final weigh would be 1 ball against another in your group of 3. The rest is trivial. That’s it folks. The answer is 3 regardless of whether it is heavier or lighter. Amen. | ||
|
Crunchums
United States11144 Posts
I can get a worst case of 4 with the second one: + Show Spoiler + Add one coin to each side, then check if each side weighs the same. Repeat this until the two sides don't weigh the same or until you weigh 5 coins against 5 coins and they still weigh the same. Once that happens, set aside the two most recently added coins or the two remaining coins if there are only two left and remove all the coins from the scale. Pick one of the two coins you set aside and weigh it against another coin that's not the other coin you set aside. If these two coins weigh the same, the fake coin is the other coin you set aside. If they do not it is the coin that you had set aside that is now on the weight scale. (This algorithm will also work with the same efficiency if you instead start with all the coins on the scale and remove them two at a time, one from each side, until it changes from not the same weight to the same weight and not measure if there are two left.) # of Measurements: Maximum - 6 Minimum - 2 Average - 3.3333... Put 3 coins on side A and 3 coins on side B and measure. If the two sides are the same weight: Add one coin to each side and measure. If the two sides are still the same weight, repeat this step unless there are now 10 coins on the scale, in which case set aside the 2 remaining coins. If the two sides are no longer the same weight, set aside the two coins you just added to each side. If the two sides are not the same weight: Remove one coin from each side and measure. If the two sides are still not the same weight, repeat this step unless there are now 2 coins on the scale, in which case set those 2 coins aside. If the two sides are now the same weight, set aside the two coins you just removed from each side. Remove all coins from the scale. Pick one of the two coins you set aside and weigh it against another coin that's not the other coin you set aside. If these two coins weigh the same, the fake coin is the other coin you set aside. If they do not it is the coin that you had set aside that is now on the weight scale. # of Measurements: Maximum - 4 Minimum - 3 Average - complicated | ||
|
SpiritoftheTunA
United States20903 Posts
| ||
|
TheYango
United States47024 Posts
On April 24 2009 09:55 Tyxiquale wrote: 2a) You take 3 balls from one end off the scale, and grab 3 "unidentified" balls from your other pile, and weigh them. If different to 3 normal balls, then it must be in that group of 3. If they are the same, then the mystery ball must be in the final 3 balls. MOST IMPORTANTLY - you know whether the ball is heavier or lighter. Uhh... HOW? ABC = DEF ABC = GHI How does that tell you whether the fake is lighter or heavier? | ||
|
Byo
Canada207 Posts
in the optimum solution, there is a case where the fake coin is not weigh'd | ||
|
SpiritoftheTunA
United States20903 Posts
On April 24 2009 09:58 TheYango wrote: Uhh... HOW? ABC = DEF ABC = GHI How does that tell you whether the fake is lighter or heavier? that flaw too what a joke lol | ||
|
Tyxiquale
Australia424 Posts
On April 24 2009 09:58 SpiritoftheTunA wrote: tyxiquale, use ABC DEF GHI JKL notation please, i think there's a flaw in your 2b but it's too ambiguous for me to evaluate Sorry for not using that notation, cos I cbf.. but there is no flaw. re-read it again. Read between the lines of what I skipped cos I thought it was too obvious. | ||
|
SpiritoftheTunA
United States20903 Posts
On April 24 2009 10:00 Tyxiquale wrote: Sorry for not using that notation, cos I cbf.. but there is no flaw. re-read it again. Read between the lines of what I skipped cos I thought it was too obvious. your signature is especially ironic, even more so since you used "their" instead of "they're" | ||
|
TheYango
United States47024 Posts
On April 24 2009 10:00 Tyxiquale wrote: Sorry for not using that notation, cos I cbf.. but there is no flaw. re-read it again. Read between the lines of what I skipped cos I thought it was too obvious. Apparently not, because Byo would have recognized your answer as correct if it were. -_- You still haven't addressed the situation I raised. | ||
|
ghostWriter
United States3302 Posts
On April 24 2009 10:01 SpiritoftheTunA wrote: your signature is especially ironic, even more so since you used "their" instead of "they're" I'm pretty sure it was done intentionally so that some high school student with a misguided sense of superiority can try to call him out on it. | ||
|
sigma_x
Australia285 Posts
| ||
|
TheYango
United States47024 Posts
On April 24 2009 10:05 sigma_x wrote: tyx is correct. The final weight of 1 ball against any of the other (two in your group) determines the solution. Ok, hold on. I'll carry out an example using his procedure. I follow it as well as i can. Balls are labeled A-L. Suppose you weigh ABC against DEF. They are the same. Step 2a says you then take GHI and weigh it against ABC. They are also the same. This says that the fake is in JKL. However, you don't know whether the fake is heavier or lighter because you've weighed 9 things that are all the same. Step 3 says weigh J with K. They are different. You still don't know which is fake without making another measurement. | ||
|
Crunchums
United States11144 Posts
edit: nevermind he's just got another way to get 4 | ||
|
TheYango
United States47024 Posts
On April 24 2009 10:09 Crunchums wrote: tyx is correct he just didn't explain very well Then explain it better, or tell me how the situation I raised is resolvable. I followed his steps, and in a worst-case scenario, it requires one more measurement. For God's sake, people, if someone doesn't understand, then explain WHY they're wrong, instead of just saying "tyx is correct, read more carefully." | ||
|
SpiritoftheTunA
United States20903 Posts
On April 24 2009 10:04 ghostWriter wrote: I'm pretty sure it was done intentionally so that some high school student with a misguided sense of superiority can try to call him out on it. it's not much of a trap like affect/effect would be why are you defending this clown | ||
|
Byo
Canada207 Posts
if weight 1 is same, and 2a is same....... and in 3, the weight are different, then which ball is the fake one? Edit: hint: + Show Spoiler + its significant whither A is > B or A is < B | ||
|
Gliche
United States811 Posts
| ||
|
SpiritoftheTunA
United States20903 Posts
On April 24 2009 10:15 Gliche wrote: tyx's way is right. It's just that is does NOT always tell you which if it's heavier or light, but that's not required according to the op. since byo didn't say that it's solved yet.. so there must be a 2nd solution? no, read the problem theyango and byo brought up if you dont know whether it's heavier or lighter within its own group, you can't find it in one more step | ||
|
FirstProbe
1206 Posts
3 is not a guaranteed maximum. | ||
|
Severedevil
United States4839 Posts
Btw, if you do it cleverly enough, you can specify which balls to weigh against which before you get the results of any of your weighings. | ||
|
FirstProbe
1206 Posts
if I weigh A against B and both weigh the same then I weigh A against C if both weigh the same then set D is the one with the fake in it. At this stage you've weighed twice. Now in set D, if I weigh D1 vs D2, and if there is a weight discrepancy, then either D1 or D2 is the fake. (weighed 3 times). In this situation you have to weigh D1 against D3 to get an answer (4th weigh). If they weigh the same then sure, you have the answer in 3 goes. Of course you can argue that if A is lighter than C, then the fake coin is heavier. In which situation, you can get the answer in 3. But so can the other such displayed answers. So in this situation, the maximum is still 4. | ||
|
nortorius
Canada1210 Posts
2.) One of the last two coins removed from part one is the fake coin. So, you weigh each coin against one of the known real coins to find out which is fake | ||
|
JeeJee
Canada5652 Posts
i'm too lazy to think it through but this question has appeared like a gazillion times before. someone on tl even wrote a formula that gives you maximum # of weightings in a generalized case of n coins | ||
|
Byo
Canada207 Posts
Not so certain you can do set weighting before knowing the results....... i could be wrong. | ||
|
Incognitodies
United Kingdom184 Posts
On April 24 2009 10:36 Byo wrote: LOL is that true, I guess I wasn't around long enough Not so certain you can do set weighting before knowing the results....... i could be wrong. You can do set weighting before knowing the results It's pretty long winded to type out though | ||
|
zobz
Canada2175 Posts
Three weighings. 1.. Weigh one group of 6 coins against the other 6 coins. 2.. Whichever group of 6 is heavier, measure 3 from that group against the other three. If these two groups of 3 weigh unequally, then the special coin must be heavier (since by the unequallity remaining within this group of 6 coins, the coin must be in this group, and since it is the heavier group of 6, the coin must be heavy). If the two groups of three in the heavier group of 6 weigh the same, the coin must be lighter, and in the other group of 6. 3.. If the special coin is in the lighter group of 6, weigh any 2 coins against each other from the lighter group of 3 within that group of 6. If the coin is in the heavier group of 6, weigh any 2 coins from the heavier group of 3 within that group of 6. If the two coins weigh equally then the remaining coin from the relevant group of 3 is the coin sought. If they weigh unequally then the special coin is the heavier one if you are weighing coins out of the heavier group of 6, or the lighter coin if you're weighing coins from the lighter group of 6. | ||
|
Slithe
United States985 Posts
3 Weighings: EFGH vs IJKL BFGK vs CDHL CEHK vs ADGL I think from the results of these 3 weighings you can always single out one of the coins to be the bad one. | ||
|
TheYango
United States47024 Posts
On April 24 2009 10:52 zobz wrote: + Show Spoiler + Three weighings. 1.. Weigh one group of 6 coins against the other 6 coins. 2.. Whichever group of 6 is heavier, measure 3 from that group against the other three. If these two groups of 3 weigh unequally, then the special coin must be heavier (since by the unequallity remaining within this group of 6 coins, the coin must be in this group, and since it is the heavier group of 6, the coin must be heavy). If the two groups of three in the heavier group of 6 weigh the same, the coin must be lighter, and in the other group of 6. 3.. If the special coin is in the lighter group of 6, weigh any 2 coins against each other from the lighter group of 3 within that group of 6. If the coin is in the heavier group of 6, weigh any 2 coins from the heavier group of 3 within [that] group of 6. If the two coins weigh equally then the remaining coin from the relevant group of 3 is the coin sought. If they weigh unequally then the special coin is the heavier one if you are weighing coins out of the heavier group of 6, or the lighter coin if you're weighing coins from the lighter group of 6. + Show Spoiler + Lemme work this out in A-L notation, just to see if I understand you correctly. ABCDEF v GHIJKL Suppose ABCDEF is heavier. Weigh ABC v DEF. If they're unequal, then the heavier one contains the fake one, and one more measurement will find it.. If they weigh the same, then the fake coin is in GHIJKL. Now here's where I stop understanding you. If the fake is in GHIJKL and GHIJKL is lighter, how do you find a group of 3 in there thats lighter without taking a measurement? You haven't weighed within GHIJKL yet, so you can't know which group of 3 is "heavier" or "lighter". | ||
|
Slithe
United States985 Posts
On April 24 2009 10:52 zobz wrote: + Show Spoiler + Three weighings. 1.. Weigh one group of 6 coins against the other 6 coins. 2.. Whichever group of 6 is heavier, measure 3 from that group against the other three. If these two groups of 3 weigh unequally, then the special coin must be heavier (since by the unequallity remaining within this group of 6 coins, the coin must be in this group, and since it is the heavier group of 6, the coin must be heavy). If the two groups of three in the heavier group of 6 weigh the same, the coin must be lighter, and in the other group of 6. 3.. If the special coin is in the lighter group of 6, weigh any 2 coins against each other from the lighter group of 3 within that group of 6. If the coin is in the heavier group of 6, weigh any 2 coins from the heavier group of 3 within [that] group of 6. If the two coins weigh equally then the remaining coin from the relevant group of 3 is the coin sought. If they weigh unequally then the special coin is the heavier one if you are weighing coins out of the heavier group of 6, or the lighter coin if you're weighing coins from the lighter group of 6. Unless I misread, I count 4 weighings if the coin is lighter. A weighing to determine which group is heavier. A weighing to determine if the coin is heavier or lighter. A weighing to find the lighter group of 3 within the lighter group of 6. A weighing to find the lighter coin from the group of 3. | ||
|
TheYango
United States47024 Posts
On April 24 2009 11:01 Slithe wrote: + Show Spoiler + 3 Weighings: EFGH vs IJKL BFGK vs CDHL CEHK vs ADGL I think from the results of these 3 weighings you can always single out one of the coins to be the bad one. + Show Spoiler + This method runs into trouble, because I and J are indistinguishable. If the first measurement is unequal, and the second 2 are equal, I or J could be the fake. The following list gives the measurement results if each coin is the fake: (E = equal, L = left is greater, R = right is greater) A - EER B - ELE C - ERL D - ERR E - LEL F - LLE G - LLR H - LRL I - REE J - REE K - RLL This could be the right way of thinking about it though. Props to you for that. | ||
|
Byo
Canada207 Posts
*edit i was too lazy to check all solutions.... perhaps all predetermined weights isn't optimum, i dunno the solution i had was..... + Show Spoiler + if abcd = efgh , i <> j, i <>k if abcd > efgh , abe > cdf, a <> b if abcd < efgh , abe > cdf, c <> d | ||
|
TheYango
United States47024 Posts
On April 24 2009 11:19 Byo wrote: there its solved..... i learned something new too lol ? Which solution solved it? Slithe's solution can't distinguish between I and J. EDIT: was Slithe's your solution in a different combination? | ||
|
Slithe
United States985 Posts
On April 24 2009 11:14 TheYango wrote: + Show Spoiler + This method runs into trouble, because I and J are indistinguishable. If the first measurement is unequal, and the second 2 are equal, I or J could be the fake. The following list gives the measurement results if each coin is the fake: (E = equal, L = left is greater, R = right is greater) A - EER B - ELE C - ERL D - ERR E - LEL F - LLE G - LLR H - LRL I - REE J - REL K - RLE This could be the right way of thinking about it though. Props to you for that. + Show Spoiler + Oh nice catch, I had a typo when converting my answer to letter format. EFGH vs IJKL BFGK vs CDHL CEHJ vs ADGL I may still have mistakes, so it would be good to verify. | ||
|
TheYango
United States47024 Posts
On April 24 2009 11:23 Slithe wrote: + Show Spoiler + Oh nice catch, I had a typo when converting my answer to letter format. EFGH vs IJKL BFGK vs CDHL CEHJ vs ADGL I may still have mistakes, so it would be good to verify. Looks good, it seems you edited the 3-measurement results that I listed, so it seems consistent now. Again, props for this way of attacking the problem. | ||
520
United States2822 Posts
12 coins problem, labeled ABCDEFGHIJKL Boolean comparison operators operate on WEIGHT, not the side that goes up or down. eg: ABCD > EFGH means that ABCD is heavier and on the bottom side of the scale First weighing: ABCD vs. EFGH Case 1: ABCD = EFGH --This means that the counterfeit is in IJKL - weight undetermined Case 2: ABCD > EFGH --Counterfeit is in one of the two groups - weight undetermined Case 3: ABCD < EFGH --Counterfeit is in one of the two groups - weight undetermined Case 1, Second weighing (Coins were even): IJK vs. ABC ABC is known to be a good group, IJK is suspect. Case 1a: IJK = ABC IJK must also be good. --Counterfeit is L - weight undetermined Case 1b: IJK > ABC IJK is heavier. --Counterfeit is in IJK and it is heavier Case 1c: IJK < ABC IJK is lighter. --Counterfeit is in IJK and it is lighter Case 2, Second weighing (Left side heavier): ABCE vs. DIJK ABCD may be heavy, E may be light, IJK are guaranteed good. Case 2a: ABCE = DIJK All of the coins tested are good. --Counterfeit is in FGH and it is lighter Case 2b: ABCE > DIJK Right side contains only good coins. --Counterfeit is in ABC and it is heavier Case 2c: ABCE < DIJK 3 good coins + 1 bad coin on either side. --Counterfeit is D and it is heavier OR counterfeit is E and it is lighter Case 3, Second weighing (Right side heavier): DFGH vs. EIJK EFGH may be heavy, D may be light, IJK are guaranteed good. Case 3a: DFGH = EIJK All of the coins tested are good. --Counterfeit is in ABC and it is lighter Case 3b: DFGH > EIJK Right side only contains good coins. --Counterfeit is in FGH and it is heavier Case 3c: DFGH < EIJK 3 good coins + 1 bad coin on either side. --Counterfeit is E and it is heavier OR counterfeit is D and it is lighter Case 1a, Third weighing (Counterfeit coin known, but not its weight, L): L vs. A Case 1a1: L < A --Counterfeit is L, L is lighter Case 1a2: L > A --Counterfeit is L, L is heavier Case 2c, 3c, Third weighing (Counterfeit is between two coins, but possible weights known, D and E): D vs. A A is known to be good, counterfeit could be either D or E. Case 2c1: D = A --Counterfeit is E, E is lighter Case 2c2: D > A --Counterfeit is D, D is heavier Case 1b, 2b, 3b, Third weighing (Counterfeit is heavy and in a group of 3 XYZ): X vs. Y Case 1b1: X = Y --Counterfeit is Z, Z is heavier Case 1b2: X > Y --Counterfeit is X, X is heavier Case 1b3: X < Y --Counterfeit is Y, Y is heavier Case 1c, 2a, 3a, Third weighing (Counterfeit is light and in a group of 3 XYZ): X vs. Y Case 1c1: X = Y --Counterfeit is Z, Z is lighter Case 1c2: X > Y --Counterfeit is Y, Y is lighter Case 1c3: X < Y --Counterfeit is X, X is lighter EDIT: Aah, looks like I got beaten to the punch. | ||
|
TheYango
United States47024 Posts
On April 24 2009 11:45 p3numbra wrote: + Show Spoiler + 12 coins problem, labeled ABCDEFGHIJKL Boolean comparison operators operate on WEIGHT, not the side that goes up or down. eg: ABCD > EFGH means that ABCD is heavier and on the bottom side of the scale First weighing: ABCD vs. EFGH Case 1: ABCD = EFGH --This means that the counterfeit is in IJKL - weight undetermined Case 2: ABCD > EFGH --Counterfeit is in one of the two groups - weight undetermined Case 3: ABCD < EFGH --Counterfeit is in one of the two groups - weight undetermined Case 1, Second weighing (Coins were even): IJK vs. ABC ABC is known to be a good group, IJK is suspect. Case 1a: IJK = ABC IJK must also be good. --Counterfeit is L - weight undetermined Case 1b: IJK > ABC IJK is heavier. --Counterfeit is in IJK and it is heavier Case 1c: IJK < ABC IJK is lighter. --Counterfeit is in IJK and it is lighter Case 2, Second weighing (Left side heavier): ABCE vs. DIJK ABCD may be heavy, E may be light, IJK are guaranteed good. Case 2a: ABCE = DIJK All of the coins tested are good. --Counterfeit is in FGH and it is lighter Case 2b: ABCE > DIJK Right side contains only good coins. --Counterfeit is in ABC and it is heavier Case 2c: ABCE < DIJK 3 good coins + 1 bad coin on either side. --Counterfeit is D and it is heavier OR counterfeit is E and it is lighter Case 3, Second weighing (Right side heavier): DFGH vs. EIJK EFGH may be heavy, D may be light, IJK are guaranteed good. Case 3a: DFGH = EIJK All of the coins tested are good. --Counterfeit is in ABC and it is lighter Case 3b: DFGH > EIJK Right side only contains good coins. --Counterfeit is in FGH and it is heavier Case 3c: DFGH < EIJK 3 good coins + 1 bad coin on either side. --Counterfeit is E and it is heavier OR counterfeit is D and it is lighter Case 1a, Third weighing (Counterfeit coin known, but not its weight, L): L vs. A Case 1a1: L < A --Counterfeit is L, L is lighter Case 1a2: L > A --Counterfeit is L, L is heavier Case 2c, 3c, Third weighing (Counterfeit is between two coins, but possible weights known, D and E): D vs. A A is known to be good, counterfeit could be either D or E. Case 2c1: D = A --Counterfeit is E, E is lighter Case 2c2: D > A --Counterfeit is D, D is heavier Case 1b, 2b, 3b, Third weighing (Counterfeit is heavy and in a group of 3 XYZ): X vs. Y Case 1b1: X = Y --Counterfeit is Z, Z is heavier Case 1b2: X > Y --Counterfeit is X, X is heavier Case 1b3: X < Y --Counterfeit is Y, Y is heavier Case 1c, 2a, 3a, Third weighing (Counterfeit is light and in a group of 3 XYZ): X vs. Y Case 1c1: X = Y --Counterfeit is Z, Z is lighter Case 1c2: X > Y --Counterfeit is Y, Y is lighter Case 1c3: X < Y --Counterfeit is X, X is lighter EDIT: Aah, looks like I got beaten to the punch. Yeah that works. I still like Slithe's solution better. Its so much more elegant!  | ||
|
520
United States2822 Posts
On April 24 2009 11:55 TheYango wrote: Yeah that works. I still like Slithe's solution better. Its so much more elegant! Actually, doesn't Slithe's say that it needs 4 weighings if the coin is lighter? Mine needs exactly 3 weighings regardless of the weight of the coin. | ||
|
TheYango
United States47024 Posts
On April 24 2009 11:57 p3numbra wrote: Actually, doesn't Slithe's say that it needs 4 weighings if the coin is lighter? Mine needs exactly 3 weighings regardless of the weight of the coin. Nah. Slithe's weighings are: EFGH vs IJKL BFGK vs CDHL CEHK vs ADGL The 3 weighings can uniquely determine which coin is fake, and what weighings you make are entirely independent of the results of previous weighings, which makes it much cleaner. | ||
|
520
United States2822 Posts
EFGH vs IJKL BFGK vs CDHL CEHK vs ADGL Case 1: EFGH = IJKL ABCD contains the miscreant coin, weight undetermined. Case 1.1: BFGK = CDHL A is the miscreant coin, BCD are all determined. Case 1.1.1: CEHK = ADGL Impossible. Case 1.1.2: CEHK > ADGL A is light. Case 1.1.3: CEHK < ADGL A is heavy. Case 1.2: BFGK > CDHL B is heavy or CD is light. Case 1.2.1: CEHK = ADGL B is heavy. Case 1.2.2: CEHK > ADGL D is light. Case 1.2.3: CEHK < ADGL C is light. Case 1.3: BFGK < CDHL B is light or CD is heavy. Case 1.3.1: CEHK = ADGL B is light. Case 1.3.2: CEHK > ADGL C is heavy. Case 1.3.3: CEHK < ADGL D is heavy. Case 2: EFGH < IJKL EFGH is light or IJKL is heavy. Case 2.1: BFGK = CDHL E is light or IJ is heavy. Case 2.1.1: CEHK = ADGL IJ is heavy. Cannot determine which. Case 2.1.2: CEHK > ADGL Impossible. Case 2.1.3: CEHK < ADGL E is light. Case 2.2: BFGK > CDHL H is light or K is heavy. Case 2.2.1 CEHK = ADGL Impossible. Case 2.2.2: CEHK > ADGL K is heavy. Case 2.2.3: CEHK < ADGL H is light. Case 2.3: BFGK < CDHL FG is light or L is heavy. Case 2.3.1 CDHK = ADGL F is light. Case 2.3.2 CDHK > ADGL G is light. Case 2.3.3 CDHK < ADGL L is heavy. Case 3: EFGH > IJKL EFGH is heavy or IJKL is light. Case 3.1: BFGK = CDHL E is heavy or IJ is light. Case 3.1.1: CEHK = ADGL IJ is light. Cannot determine which. Case 3.2.2: CEHK > ADGL E is heavy. Case 3.3.3: CEHK < ADGL Impossible. Case 3.2: BFGK > CDHL FG is heavy or L is light. Case 3.2.1: CEHK = ADGL F is heavy. Case 3.2.2: CEHK > ADGL L is light. Case 3.2.3: CEHK < ADGL G is heavy. Case 3.3: BFGK < CDHL H is heavy or K is light. Case 3.3.1: CEHK = ADGL Impossible. Case 3.3.2: CEHK > ADGL H is heavy. Case 3.3.3: CEHK < ADGL K is light. Found two flaws through rigor. | ||
|
TheYango
United States47024 Posts
On April 24 2009 12:28 p3numbra wrote: Found two flaws through rigor. Gah, I carried through his typo, the correct one was: EFGH vs IJKL BFGK vs CDHL CEHJ vs ADGL Also, rigor is a REALLY INEFFICIENT way of testing whether it works. I did an analysis in spoilers previously. | ||
|
520
United States2822 Posts
| ||
|
Chef
10810 Posts
| ||
|
micronesia
United States24698 Posts
On April 24 2009 13:01 Chef wrote: Weigh two coins against one coin and hope you get lucky on the first try. This answer is specifically incorrect in case you weren't aware since you can factor in the odds and payout of each case and you'll realize it is inferior to some of the other solutions already presented. | ||
|
Chef
10810 Posts
Then it doesn't matter how efficient the other methods are, because anymore than one try kills you. | ||
|
micronesia
United States24698 Posts
On April 24 2009 13:05 Chef wrote: What if you only have time to weigh once, or you DIE? Then it doesn't matter how efficient the other methods are, because anymore than one try kills you. I suppose if you randomly add in convenient circumstances unrelated to the original problem, then you could make a case for just about any possible solution. What a waste of time this conversation has been :p | ||
|
Chef
10810 Posts
The task is to use the scale the least number of times to determine which coin is fake. I didn't add anything. He asked what scenario will give you the least number of tries. Suppose there were a contest with 1000 people. Whoever determines which coin is fake in the least number of tries wins. You're not going to win by being slow and steady, because enough other people are going to be using the quick and dirty method that at least one will get lucky. Hah ha! | ||
|
micronesia
United States24698 Posts
On April 24 2009 13:09 Chef wrote: I didn't add anything. He asked what scenario will give you the least number of tries. Suppose there were a contest with 1000 people. Whoever determines which coin is fake in the least number of tries wins. You're not going to win by being slow and steady, because enough other people are going to be using the quick and dirty method that at least one will get lucky. Hah ha! Then why don't you just set the condition that 'whoever is first wins' and then just pick a random coin and you might be right? This is so ridiculous... | ||
|
Chef
10810 Posts
| ||
|
SpiritoftheTunA
United States20903 Posts
| ||
|
Chef
10810 Posts
Unless of course you get fucked and the fake is one of the two coins you're measuring together. Oops | ||
|
SpiritoftheTunA
United States20903 Posts
On April 24 2009 13:20 Chef wrote: I'm assuming we live in 2009 and have scales that tell you the actual weight of the coin. IE: If the one coin's weight multiplied by two is not equal to the weight of the other two coins, it's the fake. Unless of course you get fucked and the fake is one of the two coins you're measuring together. Oops ummmmm stop making shit up | ||
|
TheYango
United States47024 Posts
Hell, this blog isn't worth trolling anymore, because the OP's question has been answered in multiple ways already. | ||
|
Chef
10810 Posts
 | ||
|
minus_human
4784 Posts
Trying to explain it all here seems like a titanic task, since there are many possibilities. But the answer is 3. | ||
|
Nytefish
United Kingdom4282 Posts
I like Slithe's solution a lot more though, it's more obvious how the problem generalises too I think. | ||
|
minus_human
4784 Posts
I'm a little confused, will probably try again later My solution was basically Slithe's solution | ||
| ||
|
|
The PondCast
WardiTV Summer Champion…
herO vs MaxPax
Clem vs Classic
Replay Cast
LiuLi Cup
MaxPax vs TriGGeR
ByuN vs herO
Cure vs Rogue
Classic vs HeRoMaRinE
Cosmonarchy
OyAji vs Sziky
Sziky vs WolFix
WolFix vs OyAji
Big Brain Bouts
Iba vs GgMaChine
TriGGeR vs Bunny
Reynor vs Classic
Serral vs Clem
BSL Team Wars
Team Hawk vs Team Dewalt
BSL Team Wars
Team Hawk vs Team Bonyth
SC Evo League
TaeJa vs Cure
Rogue vs threepoint
ByuN vs Creator
MaNa vs Classic
Maestros of the Game
ShoWTimE vs Cham
GuMiho vs Ryung
Zoun vs Spirit
Rogue vs MaNa
[ Show More ] |
|
|
EPT
