# A coin-weighing puzzle with 80 coins

In 80 coins one coin is counterfeit. What is minimum number of  weighings to find out counterfeit coin?

PS: The counterfeit coin can be heavy or lighter.

-
It can't be done with weighings at all. No self-respecting counterfeiter would commit the rookie mistake of getting the mass wrong. – Henning Makholm Oct 20 '12 at 14:26
Please specify if you know whether the coin is heavy or light. That changes the process a bit. – Ross Millikan Oct 20 '12 at 14:38
@Ross The question doesn't state that the counterfeit coin has a different weight from the others. My guess is that the real coins are made of gold and the counterfeit one, although it weights the same, is made of brass, and can be distinguished from the real coins with no weighings at all. – MJD Oct 20 '12 at 15:36
@MJD: Good point. I can't imagine how to do it with less than zero weighings. – Ross Millikan Oct 20 '12 at 15:38

Hint: Consider weighing one third of the coins on each side. What will this tell you?

In fact, it can be shown that the process, the definition of which you will be led to by this hint, is optimal. Try to think of why this is the case, and to classify how many weighings you need with $n$ coins.

-

Hint: Consider weighing half of the coins on each side. What will this tell you ?

-
Then what is it ? if you have some solution write it in the question! – Belgi Oct 20 '12 at 14:27
Consider weighing one third of the coins on each side. What will this tell you? – Lord_Farin Oct 20 '12 at 15:44
@Lord_Farin - put it as an answer, very nice – Belgi Oct 20 '12 at 15:49
1. Three piles of 26, 26 and 28. Eliminate 2 piles by 1 weighing operation.
2. Worst case is 28. Make 3 piles of 9, 9, 10. Again eliminate 2 piles.
3. Worst case is 10. Make 3 piles of 3, 3 and 4. Eliminate 2 piles.
4. Worst case is 4. 3 piles of 1,1 and 2. Eliminate 2 by weighing.
5. Worst case is 2. requires another weighing operation.

Total number of weighing operations 5. I am working on solution using 4 operations.

-
You don't eliminate two piles when the coin can be either heavy or light. You do, however, know that those in one pile can only be heavy and those in the other can only be light (if the balance doesn't) or you eliminate two piles (if the balance does) – Ross Millikan Jun 5 '14 at 21:49

break the pile into a group of 26 each, leaving 2 lots of 26 and 2 coins in spare. Then weigh the lot of 26 coins alternatively to check for the defective one . similarly break the lot of 26 into 8 each leaving 2 coins in spare.continuing in this way you would get the counterfited coin in 8 attempts

-

It can be done in four weighings, assuming that you know whether the coin is heavier or lighter.

This explanation is done on the premise that it's heavier.

For the first weighing, divide the coins into three piles, two of 27 and one of 26. Weigh the piles of 27 coins.

Second weighing: if one of the piles of 27 is heavier, divide it into 3 groups of 9 and weigh two of those piles.

Third weighing: take the heavier pile of the 9 that is weighed, or if both are equal take the one that was not measured, and divide it into 3 groups of 3. Weigh two of those groups.

Fourth weighing: take the group of three that proved to be heavier and weight two of the coins, one on each side. Either one will be heavier or they will be the same, leaving the non-weighed one as the heavier one.

If both piles of 27 were the same in the first weighing, take the one of 26 coins and divide it into 2 piles of 9 and one pile of 8.

Second weighing: take the two groups of nine and weigh them, if one turns out to be heavier than the other, use steps 3 and 4 from the previous solution to find the heavier coin.

Third weighing: if the two groups of 9 were the same, take the group of 8 and divide it into 2 piles of 3 and 1 pile of 2. Weigh the two piles of 3.

If one pile of three is heavier, take it and find the heavier coin using step 4 from the previous solution.

Fourth weighing: if the two piles of three prove to be the same, weigh the two remaining coins to find the heaviest one.

-

There are 161 possibilities for the false coin, representing -80 to +80.

So the solution for a light weight 38 would be -38.

There are 161 possibilities, (including all fair),, and 161 < 243. So you can can do it in no fewer than five weighings.

Number the coins from 1 to 121, excluding #62. These are named according to the balanced trinary, but against ordinary trinary.

The revised numbers are 121+odd or 120-even.

For the five places, weigh x0xxx against x2xxx. Note the side that goes down. If neither side goes down, write x1xxx. If there is an even number of 1's, subtract the number from 22222. Subtract 11111 from the total, and you have the coin number, and + or - as heavy or light.

-