# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Author Message
Lepton
1:41+ Arse Scratcher

 Posted: Fri Jul 25, 2003 7:49 am    Post subject: 1
Timo_Tuokkola
Icarian Member

 Posted: Fri Jul 25, 2003 1:47 pm    Post subject: 2 I can find the underweight bag in 4 weighings, 5 if you need to know how much underweight the coins are. Anyone else do better? ------------------ One of the things Ford Prefect had always found hardest to understand about humans was their habit of continuously stating and repeating the very very obvious, as in It's a nice day, or You're very tall, or Oh dear you seem to have fallen down a thirty-foot well, are you all right? --The Hitchhiker's Guide to the Galaxy
David the guest
Guest

 Posted: Fri Jul 25, 2003 2:37 pm    Post subject: 3 Each weighing has 3 possible results. Therefore you need at least 4 weighings to get 81 possible results (3^4). So there can be no solution with under 4 weighings unless I am missing a trick.
casinopete
Emergency Backup Antrax

 Posted: Fri Jul 25, 2003 2:59 pm    Post subject: 4 405 gold coins seems like it would be more than several years wages at a coin weighers salary. Clearly the solution is to make off with the money. . It seems easy to improve the average weighings to less than four, but I can't yet see how to improve worst case. And since you could solve the puzzle in four weighings with only one coin from each supplier, I have a feeling it will not be the optimal answer when given five coins from each.
casinopete
Emergency Backup Antrax

 Posted: Fri Jul 25, 2003 3:10 pm    Post subject: 5 Actually, it's beginning to look quite simple to do it in three. Since you can vary the number of coins you weigh from each bag, you can test 36 vs. 36 bags, with 1-5 coins from each bag (numbers chosen so there are the same number of coins total on each side. If they balance, then the counterfeits are in one of the 9 remaining bags - a two-weigh solution. If they do not, you can weigh the same 36 vs. 36 bags, but changing the numbers of coins from each bag. Since there are 25 unique combinations of numbers-of-coins-from-a-given-bag, comparing the ratios of the weight difference from weighings 1 and 2 will narrow the choices to at most 3 ( Round (72/25) up) - which is a one-more-weighing solution. There is still leftover information, so I'm sure this strategy isn't quite fine-tuned to be the best, but I don't think there's enough to get it down to 2 weighings.  Actually, there are only 21 unique ratios (1:1 = 2:2...) so you can narrow only down to 4. But by then, you know the how different in weight the counterfeit coins are, so you can weigh those 4 as A(1 coin) + B(4 coins) vs. C(2 coins) + D(3 coins), and it will tell you exactly which one is the counterfeit. [/edit] [This message has been edited by casinopete (edited 07-25-2003 11:15 AM).]
David Guest
Guest

 Posted: Fri Jul 25, 2003 6:38 pm    Post subject: 6 Oops. I thought it was an old fangled scale. I didn't realize it gave the #. I should read more carefully. The absolute minimum is 2. Here is a solution for 2: Assign each coin a pair from the following list. Each of these pairs are reduced to the lowest common denominator. Each non zero value can have a negative sign . Each pair of distinct numbers can be flipped. That is where the multipliers come from: 0,0 0,1 * 2 * 2 1,1 * 4 1,2 * 4 * 2 1,3 * 4 * 2 1,4 * 4 * 2 1,5 * 4 * 2 2,3 * 4 * 2 2,5 * 4 * 2 3,4 * 4 * 2 3,5 * 4 * 2 4,5 * 4 * 2 There are 81 in total.
casinopete
Emergency Backup Antrax

 Posted: Fri Jul 25, 2003 6:50 pm    Post subject: 7 Elegantly answered. I knew there was a lot of information I wasn't using, but I couldn't see how it would be enough to reduce to 2.
Katherine
Guest

 Posted: Wed Jul 30, 2003 4:24 pm    Post subject: 8 Wouldn't the MINIMUM number be one? If there are 81 bags, take out one bag and place 40 each bag on the two sides of the scale. If the two piles of 40 bags are equal, you know that the one left out is the underweight bag. You'd be very lucky to do it in one, but if you're lucky, it would be possible. ? Then one more weighing would tell you how much it's off.
Lepton
1:41+ Arse Scratcher

 Posted: Wed Jul 30, 2003 5:58 pm    Post subject: 9 That is true, and it reflects critical thinking, which is a Good Thing. However, when a puzzle asks for a minimum number of something, it is usually implied that it is a worst-case scenario. In other words, you can't tell your boss "I can do it in one weighing", because you can't always do it in one weighing.
Dragon Phoenix
Judge Doom

 Posted: Wed Jul 30, 2003 7:06 pm    Post subject: 10 Checking...
dave10000
Tinhorn

Posted: Thu Jul 31, 2003 12:17 am    Post subject: 11

 Quote: In other words, you can't tell your boss "I can do it in one weighing", because you can't always do it in one weighing.

Are you suggesting that you cannot exaggerate your abilities to your boss? ? ? Faithful readers of Dilbert would disagree! (Indeed, some would suggest simply telling the boss that the bad coins are in bag # 44 and walking away -- odds are he'd never check anyway, and if he did, tell him that someone must have switched the bags.)
Lepton
1:41+ Arse Scratcher

 Posted: Thu Jul 31, 2003 3:45 am    Post subject: 12 I like to pretend that Puzzlania is utopian. It makes me feel less guilty about wasting my time here.
Beartalon
'Party line' kind of guy

 Posted: Thu Jul 31, 2003 4:38 pm    Post subject: 13 I do not understand the solution given in reply 5.
casinopete
Emergency Backup Antrax

 Posted: Thu Jul 31, 2003 5:03 pm    Post subject: 14 An explanation: The only way I can think to explain is to go ahead and describe using the solution. Bag 1 will be the 0,0 - meaning you never use a coin from this bag on either side of your scale. If both weighings result in equal results, then you know Bag 1 is from the culprit. Bag 2 will be the 0,1 - meaning you don't use any coins from it for the first weighing, but one on the right side of the scale during the second weighing. If the first result is an equal weighing, but the second shows the right side is lighter, then Bag 2 will contain the culprit. Bag 3 : 0,-1 = Weighing1(0 coins), Weighing2(1 coin on left); Culprit = Bag3 if (Result1 = even) and (Result2 = left side lighter) Bag 4 : 1,0 = Weighing1(1 coin on right), Weighing2(0 coins); Culprit = Bag3 if (Result2 = right side lighter) and (Result2 = even) Bag 5 : -1,0 ... Bag 10 : 1,2 Culprit will be if right side is light both times, and with exactly twice as much difference the second time. (having two counterfeits) Bag 11 : 1,-2 Culprit will be if right side is lighter the first time, heavier the second time, with exactly twice as much difference the second time. Bag12 : -1,2 Bag13 : -1,-2 Bag14 : 2,1 Culprit will be if right side is light both times, and with exactly half as much difference the second time. Bag15 : 2,-1 Culprit will be if right side is lighter the first time, heavier the second time, with exactly half as much difference the second time. Bag16 : -2,1 Bag17 : -2,-1 ... There are 81 distinct patterns used for the 81 bags. The list shows them all, using shorthand - the first multiplier refers to using variations of left/right on the scale (negative/positive), and the second mulitplier refers to using any given ratio's inverse (Bags 9-13 use 1/2, Bags 14-17 use 2). Since every combination gets used, each pattern is balanced by its inverse (except 0,0 which doesn't need balanced) - which means there will automatically be the same number of coins on each side.
mith
Pitbull of Truth

 Posted: Sat Aug 02, 2003 1:03 pm    Post subject: 15 A larger version of a similar problem: http://www.greylabyrinth.com/Forums/Forum5/HTML/004910.html?38
Lepton
1:41+ Arse Scratcher

 Posted: Sat Aug 02, 2003 4:58 pm    Post subject: 16 Thanks, mith. That links also appears on the page with the solution.
CrystyB
Misunderstood Guy

 Posted: Mon Aug 04, 2003 5:03 am    Post subject: 17 Hmm, why did you left out the 1,1 's, pete? Cases 6-9, 1 then 1, 1 then -1, -1 then 1, -1 then -1... That makes your statement 9-13 a typo.
casinopete
Emergency Backup Antrax

 Posted: Mon Aug 04, 2003 1:40 pm    Post subject: 18 I just thought the 1-2's illustrated more things at once. The post already takes up too much space, anyway. adn tpyos aer colo!
Jim Jackson
Icarian Member

 Posted: Wed Aug 06, 2003 2:40 pm    Post subject: 19 I'm just a country boy from North Carolina, certainly not as smart as all you who have posted these cerebral responses. I just happened to stumble onto this site and I don't solve puzzles very often. My response is pretty simple, so I could be completely missing the point here, but here goes: The boss asked him to ID the underweight bag, nothing more. The puzzle is to ID the absolute minimum needed weighs, or best case scenario. The boss said every coin in every bag weighs absolutely the same except the one bag with five underweight coins . That means 80 bags out of 81 weigh absolutely the same. The first time he puts two bags on the scale that don't weigh the same, he's found the underweight bag. He could very well pick out the underweight bag with another to weigh on his first try. If he does, the two don't weigh the same, and the lighter of the two is, of course, the underweight bag from the company the boss is looking for. The answer is one, or did I completely miss the boat? (WE might not be to smart in North Carolina, but we're mighty friendly!)
casinopete
Emergency Backup Antrax

 Posted: Wed Aug 06, 2003 2:44 pm    Post subject: 20 With the puzzle stated as it is, you are correct. I think it's clear that the intention was to ask the minimum number of weighings to [be certain you will] find the counterfeits. And that takes a second weighing, and some moderately intricate planning.
rick
Guest

 Posted: Thu Aug 07, 2003 5:13 am    Post subject: 21 Isn't this just a matter of taking 1 from bag 1, 2 from bag 2 and so on up to 5.
StormWatch
Icarian Member

 Posted: Thu Aug 07, 2003 11:20 am    Post subject: 22 I believe a minimum weighing solution of 3 is available, based on the fact you don't know the shaved amount: You need to determine the shaved amount per coin (Theoritically, a large shave on 1 coin could equal a ligher shave of 2 coins). Do a 40 side weigh and calculate the exact shave amount per coin (Weight off / 5) A Balance means you're lucky and it's the leftover bag You can split the remaining 80 bags into 5 sets of 16 Marking all of the coins, divide the 16 sets into piles of 5,4,3,2,1 coins each. Place 8 piles from each set on either side of the scale Calculate the weight off based off the known shaving weight of the coins to determine which coin count pile is off. Now it's down to 8 bags - split Pile as before and you know the specific bag. with the 3rd weigh. Anything I'm missing? [This message has been edited by StormWatch (edited 08-07-2003 07:37 AM).]
chummy_jigger
Guest

 Posted: Thu Aug 07, 2003 4:48 pm    Post subject: 23 It can be done in 3! Very similiar to an old puzzle about 9 balls.
Duke Gnome
Daedalian Member

Posted: Fri Aug 08, 2003 12:26 pm    Post subject: 24

 Quote: Anything I'm missing?

Yes, everything in replies 5 and 13
just guessing
Guest

 Posted: Sat Aug 09, 2003 6:27 am    Post subject: 25 If the boss is looking for an answer, he wants it accuratly. So throwing luck out you would have to mathmatically give him the best/worst case Scenario. To figure it out you use the division of two. there are 81 bags split them into two groups, 40 40 and set one aside and weigh (first weighing) remove the heave side and split the lighter side 20 20 (second weighing) agian remove and split 10 10 (third weighing) remove and split 5 5 (forth weighing) remove the 5 heavy ones and add the bag set aside from earlier making 6 remaining bags split and weigh 3 3(fifth weighing) remove 3 and weigh two (sixth weighing) if one is heavier than the other you have both the lightest coin and its wieght if they are equal to each other and the one set aside is the lightest. you would have to weigh it one more time of course to get the weight difference. But if you are lucky then the bag that was set aside from the beginning would be the light one. So I'm guessing the answer would go something like this. Well sir, I can do in a minimum of six weighings, maximum of seven, but if I'm lucky I'll get in one.
Beartalon
'Party line' kind of guy

 Posted: Sat Aug 09, 2003 3:06 pm    Post subject: 26 just guessing - the minimum has already been established at two weighings (we hope). Even if it wasn't, your answer is not optimal. 81 is a power of 3, so if I divide the bags like this: 27, 27, 27 - weigh two, pick whichever one is less, take the third one if they weigh the same, divide by three 9, 9, 9 - weigh two, pick whichever one is less, take the third one if they weigh the same, divide by three 3, 3, 3 - weigh two, pick whichever one is less, take the third one if they weigh the same, divide by three 1, 1, 1 - weigh two, pick whichever one is less, take the third one if they weigh the same, divide by three 4 weighings. This solution DOES NOT take into account that we can figure out how much underweight a coin is. That's why the answer can be less than 4, possibly even two. The first weighing and second weighings must include mixes of the coins from the bags in such a way that we can eliminate a maxmimum numbers of bags and also determine the weight discrepancy. StormWatch, you have to take this into account. Originally posted by The Puzzle:We don't know how much underweight these coins are, but we know they're all underweight by the same amount.There aren't multiple coins with different shavings.
Manguexa
Guest

 Posted: Mon Aug 11, 2003 4:48 am    Post subject: 27 The coin saver can be caught in three weighings . The steps are 1: Label coins to identify the bag from which they come from 2: Put coins of 40 bags in one pan and from another 40 bags in second pan but take one coin from bag one , two from bag two .... , five coins from bag five again take one from sixth , two from seventh and repeat this pattern till 40th bag in each pan . If pans are equal 81st bag is the coin saver . If the pans are unequal then the lighter one has culprit . Note the difference in weight 3: Split the lighter 40 in two groups - one in each pan . But now change the number of coins from each bag . Take 5 coins from first bag ( instead of one in previous step ) , 4 coins from bag-2 ( instead of 2 coins in step 2) , 3 coins from bag3 ( same as before ) , 2 coins from bag 4 ( instead of 4 earlier ) and 1 coin from bag 5 ( instead of 5 earlier ) and repeat the patter till 20th bag. The lighter side has the culprit . Note the weight difference . If the weight difference has remained the same then the bags from which three coins were taken ( 4 such bags) has coin saver and the difference is one third of difference. If difference has increased the coin saver is in first two bags . Again if differnce if five fold then the coin saver is from among the bags from which originally one coin was take ( again 4 such bags ) . If difference is doubled then the culprit is from bags from which 2 coins were taken originally . Same logic applies if difference is decreased . With this step the search is narrowed to 4 bags and also we know exact difference per coin Step 4 : Choose one coin from one of the four bags and two coins from second bag and put in one pan and repeat for the remaining two bags in the second pan . The lighter has culprit and from difference we can pin point the bag .
Beartalon
'Party line' kind of guy

 Posted: Tue Aug 12, 2003 5:06 pm    Post subject: 28 The solution is posted: two weighings
Rollercoaster
Daedalian Member

 Posted: Thu Aug 14, 2003 5:47 pm    Post subject: 29 Good puzzle, Zut! At first I was a little upset - I felt that this puzzle was clearly a blatant copy of my puzzle, "Catching a Groin Shaver". I see now that your solution involves math and stuff, and is not quite as 'intrusive' as my solution. So I'll let it slide.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year by All usersAnonymousBeartaloncasinopeteCrystyBdave10000Dragon PhoenixDuke GnomeJim JacksonLeptonmithRollercoasterStormWatchTimo_Tuokkola Oldest FirstNewest First
 All times are GMT Page 1 of 1

 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
You cannot post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum