80 identical coins

[Guest]

You have 80 identical coins which are all authentic, and also one counterfeit which seems identical to the others but is slightly heavier. You have three balance scales, but one of them is broken and gives random answers. How do you find the counterfeit coin in 7 weighings?

[bhramarraj]

Hi! This is an interesting approach that you and plainglazed have taken, but I'm not sure if it works. Your solution works until W5S2, but doesn't work at the end. If W5S2 gives weighing (b5) indicating that 2C1 has the heavy coin, but W6S3 gives equality indicating that 2C1 does not have the heavy coin, then you are right that one of scales 2 and 3 is random, so scale 1 is OK. But now you have only one weighing left and four possible coins, so you can't solve it.

[1] W1S1: 27A = 27B;

27C would have heavier coin. So in next weighing in balance S2, if we get result which doesn’t show 27C side heavier, then it will be confirmed that one of the balance between S1 & S2 is broken i.e. S3 is OK. Then there will be no problem in finding the heavier coin within seven weighing. So we will consider only the possibilities of getting those results in W2S2 which show 27C containing heavier coin.

Divide 27B & 27C in 14B,13B & 14C,13C.

[2] W2S2: 14B + 13C > 13B + 14C;

If [1] & [2] both are right, 13C would be heavier.

If [1] is right and [2] is wrong then 14C would be heavier.

If [1] is wrong and [2] is right then 14B would be heavier.

So in next weighing in balance S3, if we get result which doesn’t show 13C side heavier, then it will be confirmed that one of the balance between S1 & S2 is broken i.e. S3 is OK. Then there will be no problem in finding the heavier coin within seven weighing. So we will consider only the possibilities of getting those results in W3S3 which show 13C containing heavier coin. Divide 13C&13B in 7C,6C & 7B,6B.

[3] W3S3: 7C + 6B > 7B + 6C;

If All the three weighing are correct then 7C would be heavier.

If [1] & [2] are right and [3] is wrong, then 6C would be heavier.

If [1] & [3] are right then [2] can’t be wrong.

If [2] & [3] are right then [1] can’t be wrong.

So in next weighing in S1, if we get result which does not show 7C side heavier, then it will be confirmed that one of the balance between S1 & S3 is broken i.e. S2 is OK. Then there will be no problem in finding the heavier coin within seven weighing. So we will consider only the possibilities of getting those results in W4S1 which show 7C containing heavier coin.

Divide 7C in groups 4C,3C and 7B in 4B,3B.

[4] W4S1: 4C + 3B > 4B + 3C;

If all the four weighing are correct then 4C would be heavier.

If except [4], all weighing are correct 3C would be heavier.

There are no other possibilities.

So in next weighing in S2, if we get result which does not show 4C side heavier, then it will be confirmed that one of the balance between S1 & S2 is broken i.e. S3 is OK. Then there will be no problem in finding the heavier coin within seven weighing. So we will consider only the possibilities of getting those results in W5S2 which show 4C containing heavier coin.

Divide 4C in C1,C2,C3,&C4. Compare C1+C2 & C3+C4 in S2:

[5] W5S2: C1 + C2 > C3 + C4;

If all weighing are correct C1+C2 is heavier.

If all weighing except [5] are correct then C3+C4 is heavier.

There are no other possibilities.

So in next weighing in S3, if we get result which does not show C1 or C2 heavier, then it will be confirmed that one of the balance between S2 & S3 is broken i.e. S1 is OK. Then there will be no problem in finding the heavier coin within seven weighing. So we will consider only the possibilities of getting those results in W6S3 which show C1 or C2 as heavier coin.

[6] W6S3: C1 > C3

If all six weighing are correct then C1 is heavier; and if all weighing except [6] are correct, then C2 is heavier.

So in next weighing W7S1, if we get result which does not show C1 as a heavier coin, then either S3 or S1 is broken, and then C2 would be the heavier coin; or otherwise C1 is heavier coin.

I have corrected the typo error and tried to explain last two steps more clear. I am sure you will find it works. Thanks to all who encouraged me in my approach.

[bhramarraj]

[1] W1S1: 27A = 27B;

27C would have heavier coin. So in next weighing in balance S2, if we get result which doesn’t show 27C side heavier, then it will be confirmed that one of the balance between S1 & S2 is broken i.e. S3 is OK. Then there will be no problem in finding the heavier coin within seven weighing. So we will consider only the possibilities of getting those results in W2S2 which show 27C containing heavier coin.

Divide 27B & 27C in 14B,13B & 14C,13C.

[2] W2S2: 14B + 13C > 13B + 14C;

If [1] & [2] both are right, 13C would be heavier.

If [1] is right and [2] is wrong then 14C would be heavier.

If [1] is wrong and [2] is right then 14B would be heavier.

So in next weighing in balance S3, if we get result which doesn’t show 13C side heavier, then it will be confirmed that one of the balance between S1 & S2 is broken i.e. S3 is OK. Then there will be no problem in finding the heavier coin within seven weighing. So we will consider only the possibilities of getting those results in W3S3 which show 13C containing heavier coin. Divide 13C&13B in 7C,6C & 7B,6B.

[3] W3S3: 7C + 6B > 7B + 6C;

If All the three weighing are correct then 7C would be heavier.

If [1] & [2] are right and [3] is wrong, then 6C would be heavier.

If [1] & [3] are right then [2] can’t be wrong.

If [2] & [3] are right then [1] can’t be wrong.

So in next weighing in S1, if we get result which does not show 7C side heavier, then it will be confirmed that one of the balance between S1 & S3 is broken i.e. S2 is OK. Then there will be no problem in finding the heavier coin within seven weighing. So we will consider only the possibilities of getting those results in W4S1 which show 7C containing heavier coin.

Divide 7C in groups 4C,3C and 7B in 4B,3B.

[4] W4S1: 4C + 3B > 4B + 3C;

If all the four weighing are correct then 4C would be heavier.

If except [4], all weighing are correct 3C would be heavier.

There are no other possibilities.

So in next weighing in S2, if we get result which does not show 4C side heavier, then it will be confirmed that one of the balance between S1 & S2 is broken i.e. S3 is OK. Then there will be no problem in finding the heavier coin within seven weighing. So we will consider only the possibilities of getting those results in W5S2 which show 4C containing heavier coin.

Divide 4C in C1,C2,C3,&C4. Compare C1+C2 & C3+C4 in S2:

[5] W5S2: C1 + C2 > C3 + C4;

If all weighing are correct C1+C2 is heavier.

If all weighing except [5] are correct then C3+C4 is heavier.

There are no other possibilities.

So in next weighing in S3, if we get result which does not show C1 or C2 heavier, then it will be confirmed that one of the balance between S2 & S3 is broken i.e. S1 is OK. Then there will be no problem in finding the heavier coin within seven weighing. So we will consider only the possibilities of getting those results in W6S3 which show C1 or C2 as heavier coin.

[6] W6S3: C1 > C3

If all six weighing are correct then C1 is heavier; and if all weighing except [6] are correct, then C2 is heavier.

So in next weighing W7S1, if we get result which does not show C1 as a heavier coin, then either S3 or S1 is broken, and then C2 would be the heavier coin; or otherwise C1 is heavier coin.

I have corrected the typo error and tried to explain last two steps more clear. I am sure you will find it works. Thanks to all who encouraged me in my approach.

W5S2: C1+C2>C3+C4

W6S3: C1+ C3 > C2+C4

W7S1 C1 > C3

[bhramarraj]

I am still not sure of my approach.

[Guest]

A Most Unique Solution.

I'm not sure if this actually counts (even though it works).

1. Put scales one and two on each side of scale three.

2. Put 20 coins in each side of scales one and two (you do not put any coins on scale three)

A. If all three scales are balanced, all four sets of coins weight the same, and the remaining coin you have is the fake.

B. If two of three scales balance, all four sets of coins weigh the same, and the remaining coin you have is the fake. Also, the imbalanced scale is the fake one

C. If one of three scales balance, the balanced scale is an accurate scale (Note: it will be either scale one or two, it can't be scale three, the base)

D. If none of the scales balance, the third base scale is an accurate scale (The third scale must be accurate if both scales one and two are imbalanced, since at least one of the two actually has the heavy fake coin)

From here, you can simply divide the coins into groups of three and compare the weight on a gauranteed accurate scale. If this method is accepted as a single "weighing" then the answer can be obtained in only 5 measurements.

Note: I tried to be creative, but notice that the combination of three scales can also be done with three separate measurements instead if measuring them simultaneously like this is invalid. This leaves four measurements remaining, which is still enough to solve the problem since 3^4 = 81. The method of which has already been mentioned before and for brevity I won't repeat it here.

I posted this awhile ago and no one has noticed it. It gets the answer in 5 or 7 weighings depending on the validity of the first "weighing". No one has replied, and im starting to feel a little frigid in the land of the "cold shoulder"

[Guest]

I posted this awhile ago and no one has noticed it. It gets the answer in 5 or 7 weighings depending on the validity of the first "weighing". No one has replied, and im starting to feel a little frigid in the land of the "cold shoulder"

Sorry for not replying sooner.

A is correct.

B is incorrect: suppose the random scale is at the base (scale 3), with the fake coin in scale 1. Scale 1 will not be balanced, scale 2 will be balanced, scale 3 could be balanced. If so, two out of three scales are balanced, but the imbalanced scale is working and the fake coin is among the four sets.

C is incorrect: suppose scale 1 is random and scale 2 has the fake coin. Scale 2 and 3 would be imbalanced, scale 1 could be balanced. Hence we can not deduce that a single balanced scale must be working.

D is correct.

[Guest]

Ok, I have some corrections to make. Thank you for pointing them out.

First, you separate the coins into 5 groups of 16 plus one, and put one group in each dish, (17 remaining)

A. If three scales are balanced, the fake coin is in the group of 17 coins remaining. Split this group into five groups of 3 plus two and repeat (5 remaining). If you get this result a second time, split the remaining coins into 5 groups (of 1 coin each) and remeasure (1 remaining). If you get this result a third time (lucky you) the remaining coin is the fake.

B. If two scales are balanced.

1. If scale 3 (the base) is balanced, then the balanced scale on top of it is true.

2. If scale 3 (the base) is imbalanced, then the balanced scale on the "high" side of scale 3 is true.

C. If one scale is balanced, (the base scale cannot be balanced in this case)

1. if the "high" scale is imbalanced, then the balanced scale is true.

2. if the "low" scale is imbalanced, write down which scale showed what and replace the "heaviest pile" with coins from your remaining pile and measure again, refering to special case C2 mentioned below.

D. If all three scales are imbalanced, the "high" scale is random, and the "heaviest pile" (on the low side of the low scale) contains the fake.

Special Case C2: Warning: Complicated content: to make the statements more concise, we consider each balance in one of three states 1 (tilt to the left), 2 (balanced) , and 3(tilted to the right) with each number refering to balance 1 (on the left) 2, (the right) and 3 (the base). The original C2 case will be labeled 233. (you can simply rotate the stands until this result is achieved, but afterwards DON'T CHANGE IT). The results of all other cases following this one are as follows.

111: impossible after C2

112: impossible (period)

113: impossible after C2

121: impossible after C2

122: imbalanced scale is random, the remaining pile has the fake coin

123: impossible after C2

131: impossible after C2

132: impossible after C2

133: impossible after C2

211: impossible after C2

212: imbalanced scale is random, the remaining pile has the fake coin

213: scale two is random, the current "heaviest pile" contains the fake coin

221: scale three is random. the remaining pile has the fake coin

222: scale one is true, the remaining pile has the fake coin

223: scale three is random, the remaining pile has the fake coin

231: impossible after C2

232: scale two is random, the remaining pile has the fake coin

233: scale two is random, the "lighter pile" on scale two has the fake coin

311: impossible after C2

312: impossible after C2

322: scale one is random, the remaining pile has the fake coin

323: impossible after C2 (scales one and two or scales one and three can't both be fake)

331: impossible after C2 (scales one and two can't both be fake)

332: impossible after C2 (scales one and two can't both be fake)

333: impossible after C2 (scales one and two can't both be fake)

All these cases reduce the number of coins to at least 17 coins in two "weighings" and simultaneously find either a true or the random scale in two moves. With 3 moves remaining, the maximum number of coins that could be sorted is 3^3 = 27. Therefore, this method works in 5 weighings. (The A case simple speeds things up by dividing the number of remaining coins by nearly 5 when applied before this special case)

Exhausting work here.

Edited October 28, 2011 by Palustrius

[Guest]

Ok, I have some corrections to make. Thank you for pointing them out.

First, you separate the coins into 5 groups of 16 plus one, and put one group in each dish, (17 remaining)

A. If three scales are balanced, the fake coin is in the group of 17 coins remaining. Split this group into five groups of 3 plus two and repeat (5 remaining). If you get this result a second time, split the remaining coins into 5 groups (of 1 coin each) and remeasure (1 remaining). If you get this result a third time (lucky you) the remaining coin is the fake.

B. If two scales are balanced.

1. If scale 3 (the base) is balanced, then the balanced scale on top of it is true.

2. If scale 3 (the base) is imbalanced, then the balanced scale on the "high" side of scale 3 is true.

C. If one scale is balanced, (the base scale cannot be balanced in this case)

1. if the "high" scale is imbalanced, then the balanced scale is true.

2. if the "low" scale is imbalanced, write down which scale showed what and replace the "heaviest pile" with coins from your remaining pile and measure again, refering to special case C2 mentioned below.

D. If all three scales are imbalanced, the "high" scale is random, and the "heaviest pile" (on the low side of the low scale) contains the fake.

Special Case C2: Warning: Complicated content: to make the statements more concise, we consider each balance in one of three states 1 (tilt to the left), 2 (balanced) , and 3(tilted to the right) with each number refering to balance 1 (on the left) 2, (the right) and 3 (the base). The original C2 case will be labeled 233. (you can simply rotate the stands until this result is achieved, but afterwards DON'T CHANGE IT). The results of all other cases following this one are as follows.

111: impossible after C2

112: impossible (period)

113: impossible after C2

121: impossible after C2

122: imbalanced scale is random, the remaining pile has the fake coin

123: impossible after C2

131: impossible after C2

132: impossible after C2

133: impossible after C2

211: impossible after C2

212: imbalanced scale is random, the remaining pile has the fake coin

213: scale two is random, the current "heaviest pile" contains the fake coin

221: scale three is random. the remaining pile has the fake coin

222: scale one is true, the remaining pile has the fake coin

223: scale three is random, the remaining pile has the fake coin

231: impossible after C2

232: scale two is random, the remaining pile has the fake coin

233: scale two is random, the "lighter pile" on scale two has the fake coin

311: impossible after C2

312: impossible after C2

322: scale one is random, the remaining pile has the fake coin

323: impossible after C2 (scales one and two or scales one and three can't both be fake)

331: impossible after C2 (scales one and two can't both be fake)

332: impossible after C2 (scales one and two can't both be fake)

333: impossible after C2 (scales one and two can't both be fake)

All these cases reduce the number of coins to at least 17 coins in two "weighings" and simultaneously find either a true or the random scale in two moves. With 3 moves remaining, the maximum number of coins that could be sorted is 3^3 = 27. Therefore, this method works in 5 weighings. (The A case simple speeds things up by dividing the number of remaining coins by nearly 5 when applied before this special case)

Exhausting work here.

Nicely done

[bhramarraj]

Let us first solve the case for 9 coins. Let us name the coins as 1A1, 1A2, 1A3, 1B1, 1B2, 1B3, 1C1, 1C2, & 1C3.

W1S1: 1A1+1A2+1A3 v/s 1B1+1B2+1B3.

W2S2: 1A1+1B1+1C1 v/s 1A2+1B2+1C2.

W3S3:: We weigh the group of coins which possibly contain heavier coin according to the above two weighing, excluding the coin which is common.

For example say: W1S1: 1A1+1A2+1A3 = 1B1+1B2+1B3. (1C1, 1C2, or 1C3 is heavier)

W2S2: 1A1+1B1+1C1 = 1A2+1B2+1C2. (1A3, 1B3, or 1C3 is heavier)

1C3 is common in the results of above two weighing. So we compare 1A3, 1B3, & 1C1, 1C2 in third weighing.

W3S3: 1A3+1B3 v/s 1C1+1C2

It is given in OP that only one balance is broken. Therefore at least two of the above three results must be correct. So:

[1] If the third weigh shows both pans equal, then definitely 1C3 is the heavier coin.

[2] If the third weigh shows LHS > RHS, then results of W1S1 & W3S3 contradicts each other, which indicates either the S1 or S3 balance is broken. So S2 balance must be Good. Then comparing two coins out of 1A3, 1B3, & 1C3 in fourth weigh in S2 will reveal the heavier coin.

[3] If the third weigh shows LHS < RHS, then results of W2S2 & W3S3 contradicts each other, which indicates either the S2 or S3 balance is broken. So S1 balance must be good. Then comparing two coins out of 1C1, 1C2, & 1C3 in fourth weigh in S1 will reveal the heavier coin. So for 9 coins we need max 4 weighing to find out heavier coin.

Now for 81 coins ......?

First divide the coins in 9 groups of 9 coins each. Name them: 9A1, 9A2, 9A3, 9B1, 9B3, 9C1, 9C2, 9C3.

W1S1: 9A1+9A2+9A3 v/s 9B1+9B2+9B3

W2S2: 9A1+9B1+9C1 v/s 9A2+9B2+9C2

W3S3: Comparing the groups of coins possibly containing the heavier coin, according to the above two weighing. For example,

W1S1: 9A1+9A2+9A3 = 9B1+9B2+9B3. (9C1, 9C2, or 9C3 is heavier)

W2S2: 9A1+9B1+9C1 = 9A2+9B2+9C2. (9A3, 9B3, or 9C3 is heavier)

9C3 is common in the results of above two weighing. So we compare 9A3, 9B3, & 9C1, 9C2 in third weighing.

W3S3: 9A3+9B3 v/s 9C1+9C2

It is given in OP that only one balance is broken. Therefore at least two of the above three results must be correct. So:

[1] If the third weigh shows both pans equal, then definitely 9C3 is the heavier group. Now As explained in case of 9 coins, next max four weighing will decide the heavier coin.

[2] If the third weigh shows LHS > RHS, then results of W1S1 & W3S3 contradicts each other, which indicates either the S1 or S3 balance is broken. So S2 balance must be Good. Then comparing two groups out of 9A3, 9B3, & 9C3 in fourth weigh in S2 will reveal the heavier group of 9 coins. Then subsequent two weighing in S2 will reveal the heavier coin.

[3] If the third weigh shows LHS < RHS, then results of W2S2 & W3S3 contradicts each other, which indicates either the S2 or S3 balance is broken. So S1 balance must be good. Then subsequent two weighing in S1 will reveal the heavier coin.

Thus we see Max 7 weighing are required to find out the heavier coin in case of 81 coins.

[bhramarraj]

Let us first solve the case for 9 coins. Let us name the coins as 1A1, 1A2, 1A3, 1B1, 1B2, 1B3, 1C1, 1C2, & 1C3.

W1S1: 1A1+1A2+1A3 v/s 1B1+1B2+1B3.

W2S2: 1A1+1B1+1C1 v/s 1A2+1B2+1C2.

W3S3:: We weigh the group of coins which possibly contain heavier coin according to the above two weighing, excluding the coin which is common.

For example say: W1S1: 1A1+1A2+1A3 = 1B1+1B2+1B3. (1C1, 1C2, or 1C3 is heavier)

W2S2: 1A1+1B1+1C1 = 1A2+1B2+1C2. (1A3, 1B3, or 1C3 is heavier)

1C3 is common in the results of above two weighing. So we compare 1A3, 1B3, & 1C1, 1C2 in third weighing.

W3S3: 1A3+1B3 v/s 1C1+1C2

It is given in OP that only one balance is broken. Therefore at least two of the above three results must be correct. So:

[1] If the third weigh shows both pans equal, then definitely 1C3 is the heavier coin.

[2] If the third weigh shows LHS > RHS, then results of W1S1 & W3S3 contradicts each other, which indicates either the S1 or S3 balance is broken. So S2 balance must be Good. Then comparing two coins out of 1A3, 1B3, & 1C3 in fourth weigh in S2 will reveal the heavier coin.

[3] If the third weigh shows LHS < RHS, then results of W2S2 & W3S3 contradicts each other, which indicates either the S2 or S3 balance is broken. So S1 balance must be good. Then comparing two coins out of 1C1, 1C2, & 1C3 in fourth weigh in S1 will reveal the heavier coin. So for 9 coins we need max 4 weighing to find out heavier coin.

Now for 81 coins ......?

First divide the coins in 9 groups of 9 coins each. Name them: 9A1, 9A2, 9A3, 9B1, 9B3, 9C1, 9C2, 9C3.

W1S1: 9A1+9A2+9A3 v/s 9B1+9B2+9B3

W2S2: 9A1+9B1+9C1 v/s 9A2+9B2+9C2

W3S3: Comparing the groups of coins possibly containing the heavier coin, according to the above two weighing. For example,

W1S1: 9A1+9A2+9A3 = 9B1+9B2+9B3. (9C1, 9C2, or 9C3 is heavier)

W2S2: 9A1+9B1+9C1 = 9A2+9B2+9C2. (9A3, 9B3, or 9C3 is heavier)

9C3 is common in the results of above two weighing. So we compare 9A3, 9B3, & 9C1, 9C2 in third weighing.

W3S3: 9A3+9B3 v/s 9C1+9C2

It is given in OP that only one balance is broken. Therefore at least two of the above three results must be correct. So:

[1] If the third weigh shows both pans equal, then definitely 9C3 is the heavier group. Now As explained in case of 9 coins, next max four weighing will decide the heavier coin.

[2] If the third weigh shows LHS > RHS, then results of W1S1 & W3S3 contradicts each other, which indicates either the S1 or S3 balance is broken. So S2 balance must be Good. Then comparing two groups out of 9A3, 9B3, & 9C3 in fourth weigh in S2 will reveal the heavier group of 9 coins. Then subsequent two weighing in S2 will reveal the heavier coin.

[3] If the third weigh shows LHS < RHS, then results of W2S2 & W3S3 contradicts each other, which indicates either the S2 or S3 balance is broken. So S1 balance must be good. Then subsequent two weighing in S1 will reveal the heavier coin.

Thus we see Max 7 weighing are required to find out the heavier coin in case of 81 coins.

shakingdavid and plainglazed, may please comment.......!

Edited June 5, 2012 by bhramarraj