# Answer to the Friday Puzzle….

39

On Friday I posed this problem….You are given eight coins and told that one of them is counterfeit. The counterfeit one is slightly heavier than the other seven. Otherwise, the coins look identical. Using a simple balance scale, how can you determine which coin is counterfeit using the scale only twice?

If you have not tried to solve it, have a go now.  For everyone else the answer is after the break.

Start off by weighing three of the coins against three others. If the weights are equal, weigh the remaining two against each other. The heavier one is the counterfeit. If one of the groups of three is heavier, weigh two of those coins against each other. If one is heavier, it’s the counterfeit. If they’re equal weight, the third coin is the counterfeit.

Did you solve it? Any other answers?

I have produced an ebook containing 101 of the previous Friday Puzzles! It is called PUZZLED and is available for the Kindle (UK here and USA here) and on the iBookstore (UK here in the USA here). You can try 101 of the puzzles for free here.

1. M says:

Got it, but seen the puzzle before

• Vo says:

Using Statistics and Probability, the best way is to compare 1 by 1. The expected value is (2/8)*1 + (6/8)*2 = 1.75. On average you would balance 1.75 times

2. Goliath says:

Wow, I’m on a winning streak. I got the Friday puzzle right two times in a row.

*off to gamble in the cinema*

3. Anders says:

Yes, a variation on an old theme. I’m still wondering if there is an optimal strategy for the general case…

• Anonymous says:

Same strat as for this one? Maximum amount of coins you can exclude is 2/3 for every weighing.
-> 1-3 coins 1 weighing.
4-9 coins -> 2 weighings
10-27 coins -> 3 weighings
ect

• Nanda Gunawardhana says:

Coins times

1 0
3 1
7 2 (this case)
15 3

2^n -1 n-1 for (n>2)

• Anders says:

Yes, but for example in the 10 coin case, you have a worst case scenario of 3 weighings. But if you do 4-4 in the first weigh, and they balance (which they will on average 20% of the time) you get the correct coin on the second weigh, so an average of 2.8. That’s what I mean by an optimal strategy, trying to minimize the average case.

• Anders says:

…and as I typed that, I realized you can get it down even further, by weighing 3-3 the first time. If they don’t match (60% of the time) the coin is found on the next attempt, so an average of 2.4 weighings

• Anders says:

Thinking even more on it, I can get it down even further.

First: 3-3 -> if unbalanced, next will solve
Second (if first is balanced): 1-1 of the 4 remaining.
Third (if second is balanced): 1-1 of the 2 remaining.

This works out to an average of 2.2 operations for 10 coins. I wonder if that is optimal or if it’s possible to reduce it even further.

I’m beginning to feel like I’m optimizing code 🙂

• Yat says:

@Anders
As there are 10 coins, there are 10 different possible scenarios, each one with a probability of 1/10.

First, let’s assume that in every scenario, you need at least 2 weighs to determine the fake coin.
It is not possible to win in 2 weighs in every scenario, because that makes only 9 combinations. We can conclude that there is at least one case (one specific fake coin) which requires 3 weighs. Now, if we suppose that there is only one, then 2 weighs would be enough to determine the fake coin in the 9 other cases. If we are not in one of these 9 cases we can deduce that the fake coin is the tenth, which would then be determined in 2 weighs too, this is a contradiction (we could also state that if there is a third weigh, its purpose is to decide between at least 2 possibilities).
The first conclusion is that If you need at least 2 weighs in every case, then you need at least 3 weighs in at least 2 cases out of 10. That makes your 2.2 the smallest possible average cost under this first assumption.

Now, let’s forget the first assumption and try to beat 2.2.
To find a fake coin on the first weigh, you either need it to be the only one left out (which leaves an odd number of coins to weigh, bad idea), or to be the only one on its plate. Therefore you can only weigh 2 coins, and you win in 1 weigh with a probability of 1/5. If you did not, you are left with 8 suspicious coins, and you need to find the fake one in an average of 1.5 additional weighs (2.2 = (2*1+8*2.5)/10). This is less than 2, which implies that there must be some scenarios where you find the fake coin in one additional weigh. Using the same reasoning as before you burn one weigh to detect 2 coins, and are left with 6, and an average of 0.666.. weighs (2.2 = (2*1+2*2 + 6*2.666..)/10). Ok… this implies that some cases can be solved in 0 additional weighs, which seems unlikely.

Conclusion : you can stop looking, an average of 2.2 operations is the lower bound. Congrats !

4. Charles Sullivan says:

Yes. Thanks. I can’t solve most of these, but I got this one. I realized that weighing 4 against 4 would require at least 3 weighings, so I considered 3 against 3…..presto!!!!

5. Steve Jones says:

If people want a more difficult variation on this, the most common form of this problem is to have 12 coins with one counterfeit which is a different weight from the other 11 (but you don’t know if it’s heavier or lighter). Using a simple balance, find a strategy that uses the least number of operations to find the counterfeit coin..

max 4 operations.

• Yat says:

@RaduV : can be done in 3. Planned in advance if you want to spice things up 😉

@Yat: Thinking hard on the 3 operation method, but i don’t find any solution. If i don’t get it until tomorrow, I’ll ask you for a hint 🙂

• aflame says:

The key to the ‘unknown weight’ variations is using the coins that you know for sure are real 😉

• Yat says:

@aflame
That’s a way to look at it. This key does not make much sense if you plan the weighs ahead.

6. rmb says:

Why limit to eight coins. I think nine coins can be checked in two weighing with this strategy.

• Amanda Huggenkiss says:

Probably because if you have an odd number of coins it would make it obvious that you aren’t supposed to weigh them all at the same time, which is the major clue to the successful strategy.

• JimC says:

I think limiting the question to eight coins makes the puzzle slightly harder, by setting up the “divide by 2” red herring, which I originally fell for on Friday. Nine can only be divided by three, so an entire line of reasoning is eliminated right off the bat.

• Anonymous says:

do you know how? if so can you explain?

7. ChasTiv says:

Missed it. I started with 4 against 4, and got lost.

btw: Steve’s variation (above) with 12 coins has an ingenious solution without needing any “if…” branches, which your 8-coin problem needed.

• Yat says:

Actually, the 8-coin problem does not either. For example, do the following weighs :
A+B+C vs D+E+F
A+D+G vs B+E+H
See ? no “if” branch needed, and both results are enough to determine which is the fake coin.

• Steve Jones says:

@yat

Indeed, those sort of strategies work best of all. However, they are rather mathematical in their nature and don’t seem to be natural to the way people’s minds work. For most people I suspect the step-wise logic of the “if then” approach is easier to appreciate, even if, mathematically speaking, yours is more elegant.

• Yat says:

@Steve
Obviously ! 😉

8. Puddleglum says:

My class on a Friday morning have started to demand to have a go at the Friday puzzle. We really enjoyed this one – thanks Richard.

9. That is a great puzzle. I wish i had put more effort into finding the answer. But usually your puzzles have some silly twist so I thought this one would too, so I didn’t bother thinking about it more than a couple of minutes. I regret it now cause I love that kind of puzzle!

10. Danielle says:

I may be reading it wrong, but I’m a little confused. If one of the three is heavier, and so you weigh two of each three on either side, and still one of those is heavier, how do you know which it is? I understand if they were weighted more one way before, then you removed one and it balanced that that’s the heavier one…. But maybe I’m just too sleepy to get it right now!

you read it wrong. When you find the 3 coins that are heavier, you pick 2 coins from there and weigh then. If the coins are equal, then the remaining one is the heavier one.

11. Lazy T says:

I remember this puzzle using whales,not coins, they had to be taken to a whale-weigh station.

12. Zach says:

Here’s how I solved: weigh 4 against 4. one side will be slightly heavier, so take those 4 coins and weigh 2 against 2. again, one side will be heavier, so take those 2 coins and just judge in your hand which is heaviest (the problem said nothing about coins’ weight difference being so subtle that they couldn’t be compared by hand).

• Goliath says:

You technically weighed the coins three times which is, according to the problem, not allowed.

13. h8of9@yahoo.com says:

I remembered this puzzle from long ago but suspected that you might be throwing a curve.(“The counterfeit one is slightly heavier than the other seven.”) If the one coin weighed more than the other seven combined, I doubt you would need a scale at all.

14. Will says:

15. Eureka! This was one of the easiest to date.

16. Henry Ruddle says:

For the longest time I was stuck on keeping the coins on the scale, but 4 against 4, followed by 2 against 2 would require 3 weighings. Finally I realized … duh .. that if the subset weighed was balanced the odd coin out would be the counterfeit. Once the false assumption was cleared, it was easy.

17. Jerry says:

Yep. (:-)

18. Thanks for game. It will give good fun and learned lot of tricks to play this game and addicted to this

You can also play more puzlles games clickazoid puzzle games

19. Anonymous says:

how do you do this for 9 coins and 2 weighings?