Discuss Catching a Coin Shaver here

[Lepton]

Puzzle Link

[Timo_Tuokkola]

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]

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]

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]

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.

[edit]
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]

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]

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]

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]

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]

Checking...

[dave10000]

[Lepton]

I like to pretend that Puzzlania is utopian. It makes me feel less guilty about wasting my time here.

[Beartalon]

I do not understand the solution given in reply 5.

[casinopete]

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]

A larger version of a similar problem: http://www.greylabyrinth.com/Forums/Forum5/HTML/004910.html?38

[Lepton]

Thanks, mith. That links also appears on the page with the solution.

[CrystyB]

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]

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]

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]

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]

Isn't this just a matter of taking 1 from bag 1, 2 from bag 2 and so on up to 5.

[StormWatch]

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]

It can be done in 3!
Very similiar to an old puzzle about 9 balls.

[Duke Gnome]

[just guessing]

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]

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]

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]

The solution is posted: two weighings

[Rollercoaster]

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.