Friday Puzzler -- Counterfeits

Re: Friday Puzzler -- Counterfeits

Alex Y

P.S., I really did write this on Friday, then checked in today to see if there were any responses, and saw I had never hit the "post" button.

Re: Friday Puzzler -- Counterfeits

Larry Barrett

Label the bag with the fair coins X and the bag with the counterfeit coins Y.

From the problem statement, X contains only fair (F) coins; Y contains a mix of light (L) coins and heavy (H) coins, but no F coins. Furthermore, Y must contain exactly the same number of L coins and H coins; otherwise Y would not balance with X.

Let's start with a simpler problem. Same setup, but just 2 coins in each bag.

This is easy. Take the two coins out of one bag and place them on the balance. If you selected X, the coins will balance. If you selected Y, the coins will not balance.

Now assume each bag contains 4 coins. Select a bag, remove the 4 coins, divide into 2 piles of 2 each and place on balance. If you selected X the coins will balance (FF = FF). If you selected Y, and you divided the coins into LL and HH, they will not balance and you would know that Y has the counterfeit coins. But if you divided the coins into LH and HL, they would balance.

So after the first division, you know that you either have FF = FF or LH = HL. Now take all coins off the balance but retain the separate piles. Select any pile and place one coin on each side of the balance. You could have selected FF, FF, LH, or HL. The coins will balance only if you selected FF or FF. Thus you know which bag has the counterfeits.

I think this can be extended to the case where each bag contains 32 coins. It seems like it gets complicated quickly.

Good for 5. Can you beat that?

Alex Y

The solution you describe is to ignore one bag, then with the other bag, take wieghings as follows, stopping if you ever get an uneven weight.

1) 16 v 16

2) return one of the piles of 16 to the bag, and split the other and weigh 8 v 8

3) 4 v 4

4) 2 v 2

5) 1 v 1

In each case, the only way to get a balance if you are working with the counterfeits is for each side to be half lights and half heavies (which of course cannot be possible in #5, so you are guaranteed a resolution no later than that).

Surprisingly, this is not optimal, though. There is a way to determine with fewer weighings.

Target

Alex Y

It is possible to determine which bag has counterfeits with only two additional weighings. How?

Solution

Alex Y

Divide one of the bags into piles of 11, 11, and 10 coins.

1) compare the two piles of 11. If they do not balance, you are dealing with the counterfeits.

2) remove ten coins from one side of the scale, and replace them with the ten coins that have not yet been weighed. If the two sides do not balance, you are dealing with counterfeits. If they do balance, you are dealing with fair coins.

I'll post why it works in another post, in case you want to puzzle this one out -- it was far from obvious to me.

Why this works

Alex Y

Obviously, if you get an imbalance at any point, you are dealing with the counterfeits, and if you are dealing with fair coins, everything will balance. So we just need to see if it is possible to get balances in both these weighings with the counterfeits.

By the problem statement, we can deduce that the bag of counterfeits consists of 16 heavies and 16 lights.

In the initial weighing, since we are dealing with an odd number of coins, both sides are heavy or both sides are light. We'll assume heavy; the same argument applies if they are both light.

Because both sides are heavy, we know that each side contains at least 6 heavies. Since the bag contained 16 heavies, that means the ten not initially weighed include at most 4 heavies, and at least 6 lights.

No matter which coin you left on the scale to combine with these ten, the result will be 11 coins that have at least 6 lights and at most 5 heavies, so won't balance.