Balancing Gold Coins

[gavinksong]

A reversal of a classic problem.

You have a bag of gold coins. They are all of the exact same weight except one, which is a fake.

You have a balance scale, which you can only use N times. What is the maximum number of coins from which you can pick out the fake?

[CaptainEd]

First, I define Restricted and Unrestricted coins, then describe and prove the algorithm for Restricted coins. Next, I request a slight tweak to the OP conditions--one additional coin known to be good. Then comes the definition of the procedure for Unconstrained coins, followed by the edge case (how many coins with only one weighing), and the formula for the Unconstrained case, since the OP requests the Unconstrained formula. 
Then come the first few values.

Spoiler

a Restricted coin is one that has been in a pan that failed to balance. A coin that was in the heavy pan is H (good or heavy), a coin that was in a light pan is an L (good or light). An Unconstrained coin is one that has not yet been weighed.

 

Spoiler

Induction hypothesis: One misweighted coin can be found from 3^p Restricted coins in p weighings.

Proof by induction on P
P=1: given 3 Restricted coins, pick 2 that match (i.e. Are both H or both L). Weigh the two against each other. If they balance, the remaining coin is the bad one. If they don't balance, the bad coin is the one that matches the behavior. That is, if both coins are H, then the one in the heavy pan; or if both coins are L, then the one in the light pan. The coin was isolated in 1 weighing.

P>1: given 3^p Restricted coins, set aside 3^(p-1) coins, and divide the others into two pans, in any pattern as long as number of H coins in each pan are equal, and number of L coins in each pan are equal (either number could be zero, it's ok)
 
Now weigh the two pans. If they balance, the bad coin is in one of the 3^(p -1) restricted coins that were set aside. According to induction hypothesis, it will take an additional p-1 weighings to find the bad coin.
If they don't balance, one side is heavier than the other. There are exactly 3^(p -1) coins that could cause that side to be heavy: the H coins in that pan, plus the L coins in the opposite pan. Thus, the bad coin is one of those 3^(p -1) coins, and once again it will take p-1 weighings to find the bad coin.

So in both cases, we have performed one weighing, and it will take p-1 more weighings. Therefore it will take p weighings to locate the bad coin out of 3^p Restricted coins. Induction step is proved.

 

Spoiler

So imagine the function R(n), the number of Restricted coins from which the bad coin can be found in n weighings.
R(n) = 3^n

But we had to perform one weighing in order to make all these Restricted coins. Can't we learn something additional from that weighing? Yes! If they balance, then we could pursue additional coins.

I need to request an OP boon ("a boon, Sire!") :

Spoiler

please allow me to have one additional coin that is known to be good. My justification is uniformity: at every level, we need a known Good coin, and we've already identified some. But the initial weighing could also benefit from 1 known good coin, and we don't have one. 

Spoiler

Now consider U(n), the number of Unrestricted coins from which the bad coin can be found in n weighings.
Follow this strategy. Create 3^n Restricted coins by weighing 1 Good coin and 3^n Unrestricted coins in the two pans. If they don't balance, then you have identified 3^n Restricted coins, and it will take n more weighings to find it.
If they do balance, the remaining coins are Unrestricted coins, and we can perform the same algorithm, with one fewer weighings.
So U(n) = R(n-1) + U(n-1)
Recursively, this works out to 
U(n) = R(n-1) + R(n-2) + ... + R(1) + U(1). 

Spoiler

U(1) is interesting (and perhaps open to debate). Notice that U(0) = 1. That is, if you're given 1 coin and you're told one coin is bad, you can identify it with zero weighings. 

How many can you distinguish with 1 weighing? If The Boon is granted, you can distinguish 2 Unrestricted coins in 1 weighing, as follows.

Place one coin in one pan , place the Known Good coin in the other pan, and set another coin aside. 
If they balance, the bad coin is the one that was set aside. If they don't, the bad coin is the one opposite the Good coin.
So, with this OP-granted boon, U(1) = 2.

 

Spoiler

The first few values of U(n):
U(2) = R(1) + U(1) = 3 + 2 = 5
U(3) = R(2) + R(1) + U(1) = 9 + 3 + 2 = 14
U(4) = 27 + 9 + 3 + 2 = 41
U (5) = 81 + 27 + 9 + 3 + 2 = 122

 

[BMAD]

If the bag contains coins that equal 2^m then it would take m+1 try to find the fake coin. 

The spoiler option seems to have disappeared from the mobile app. 

[gavinksong]

10 minutes ago, BMAD said:

Spoiler

If the bag contains coins that equal 2^m then it would take m+1 try to find the fake coin.

 

I think I see the intuition behind that guess, but alas that is not it. Counterexample in the spoiler.

Spoiler

To rephrase your response, the maximum number of coins is 2^(n-1). So with three uses of the balance scale, you should only be able to pick out the fake from at most 4 coins.

However, in the original problem, you have 12 coins, and you are allowed three uses of the balance scale. (Hint: do not let this example mislead you. The original problem is possible with more than 12 coins.)

 

[BMAD]

19 hours ago, gavinksong said:

I think I see the intuition behind that guess, but alas that is not it. Counterexample in the spoiler.

  Hide contents

To rephrase your response, the maximum number of coins is 2^(n-1). So with three uses of the balance scale, you should only be able to pick out the fake from at most 4 coins.

However, in the original problem, you have 12 coins, and you are allowed three uses of the balance scale. (Hint: do not let this example mislead you. The original problem is possible with more than 12 coins.)

 

I don't see how that's possible if we don't know whether the fake is heavier or lighter in advance. 

[gavinksong]

9 minutes ago, BMAD said:

I don't see how that's possible if we don't know whether the fake is heavier or lighter in advance. 

I will confirm that it is possible even when it is not known whether the fake is lighter or heavier.

In your first guess, you had a power of two, which makes me think you were inspired by binary search. Remember that a balance scale has three possible outcomes.

Even then, the answer is not as simple as 3^n/2.

Edited August 11, 2017 by gavinksong

[gavinksong]

18 minutes ago, gavinksong said:

Even then, the answer is not as simple as 3^n/2.

Actually, I just did the math...

Spoiler

... and the answer is almost that simple.

 

[Donald Cartmill]

The maximum number of coins for the solution is 3.  This is basically what you arrive at when deriving the odd coin in a group of 12 ,allowing only 3 weighings, the maximum number for a solution is 3.      Bottom line is that step 1) taking 1/3 of the coins on each pan and leaving 1/3 off. If they balance then step 2) divide those  previously left off again into 1/3 on each pan and 1/3 off.  3) You will continue this until you are down to 3 coins.  Then 1 on each pan , if they balance then the one left off is the odd coin.    A)  Now if at any time the number of coins is not evenly divisible by 3 ,then the left over coins go in the pile left off.    B) If at any time during the early stages the pans do not balance , you will remove the right pan coins and divide the left pan into half placing 1/2 on each pan...they balance ,then the odd is obviously in the group removed from the right pan and  start again at step 2)    Now if they do not balance repeat B)   

[Donald Cartmill]

The number is 3 coins

[gavinksong]

2 hours ago, Donald Cartmill said:

The maximum number of coins for the solution is 3.

I'm sorry if I wasn't clear. I was asking for an answer in terms of N (number of weighings allowed).

After all, the maximum number of coins from which you can pick out the fake is not constant and in fact increases with N.

2 hours ago, Donald Cartmill said:

Spoiler

Bottom line is that step 1) taking 1/3 of the coins on each pan and leaving 1/3 off. If they balance then step 2) divide those  previously left off again into 1/3 on each pan and 1/3 off.  3) You will continue this until you are down to 3 coins.  Then 1 on each pan , if they balance then the one left off is the odd coin.    A)  Now if at any time the number of coins is not evenly divisible by 3 ,then the left over coins go in the pile left off.    B) If at any time during the early stages the pans do not balance , you will remove the right pan coins and divide the left pan into half placing 1/2 on each pan...they balance ,then the odd is obviously in the group removed from the right pan and  start again at step 2)    Now if they do not balance repeat B)   

 

On the other hand, the method you outlined is a reasonable first attempt. You do have one blind spot...

Spoiler

... in step 3B. There aren't necessarily an even number of coins in the right pan.

It is possible to calculate the maximum number of coins your method could work for (in terms of N).

Spoiler

In the worst case scenario, your method uses the scale twice each time it reduces the number of suspects by a factor of 3. Therefore, the scale could potentially be used 2 * log_3(# of coins) times. The maximum number of coins your method would work for is 3^(N/2), which is less than even 2^N.

There is a more efficient method that works for larger numbers of coins.

P. S. It is common to hide any revealing content inside spoilers (like I did above). The "eye" icon on the very left of the toolbar allows you to insert them into your responses.

Edited August 11, 2017 by gavinksong
wording

[CaptainEd]

[spoiler=answer maybe]in N weighings, can distinguish bad coin out of M=Sum(3^i), i=0...N-1

Can't always tell whether heavy or light[/spoiler]

[spoiler=Background: restricted vs unrestricted]if you weigh coins in the balance scale, and the Left pan is heavy, then the coins in that pan are "restricted": each one is either Good or Heavy, while the coins in the other pan are restricted as either Good or Light. I abbreviate "heavy or good" as "H", and "light or good" as "L". 

We can distinguish among 3^N restricted coins in N weighings. 

[/spoiler]

[spoiler=Strategy]However, we are starting with coins we know nothing about (and maybe one coin known to be good)

So we will weigh a number of coins (p), leaving some of them (q) unweighed. Once you weigh the first batch, they become restricted, and you can resolve one of them in ceil(log base 3 (p)).  If they balanced, then you have N-1 weighings to resolve the remaining q coins. So our initial task when approaching a set of coins is to choose p and q so that the number of weighings for p restricted coins equals number of weighings for q unrestricted coins. [/spoiler]

[CaptainEd]

sorry, my attempt to remove the post failed. 

[gavinksong]

On August 14, 2017 at 2:50 AM, CaptainEd said:

Spoiler

in N weighings, can distinguish bad coin out of M=Sum(3^i), i=0...N-1

Can't always tell whether heavy or light

 

This is actually correct! Another way to write it:

Spoiler

We can always pick out the fake coin out of a bag of (3^n - 1)/2 gold coins.

However, your rationale has a few loose ends. I am interested in seeing your full solution.

Spoiler

1. You claimed that "We can distinguish among 3^N restricted coins in N weighings." Can you prove that this is always possible?
2. In the first step, how many coins do you leave unweighed?

Equivalently, what is an explicit algorithm?

[CaptainEd]

cant do this compactly with iPhone. I'll answer sooon. (1) yes I'll make better demonstration about Restricted approach. (2) yes, I'll describe complete Unrestricted approach, which gives larger number

[gavinksong]

15 hours ago, CaptainEd said:

First, I define Restricted and Unrestricted coins, then describe and prove the algorithm for Restricted coins. Next, I request a slight tweak to the OP conditions--one additional coin known to be good. Then comes the definition of the procedure for Unconstrained coins, followed by the edge case (how many coins with only one weighing), and the formula for the Unconstrained case, since the OP requests the Unconstrained formula. 
Then come the first few values.

  Reveal hidden contents

a Restricted coin is one that has been in a pan that failed to balance. A coin that was in the heavy pan is H (good or heavy), a coin that was in a light pan is an L (good or light). An Unconstrained coin is one that has not yet been weighed.

 

  Hide contents

 

  Hide contents

Induction hypothesis: One misweighted coin can be found from 3^p Restricted coins in p weighings.

Proof by induction on P
P=1: given 3 Restricted coins, pick 2 that match (i.e. Are both H or both L). Weigh the two against each other. If they balance, the remaining coin is the bad one. If they don't balance, the bad coin is the one that matches the behavior. That is, if both coins are H, then the one in the heavy pan; or if both coins are L, then the one in the light pan. The coin was isolated in 1 weighing.

P>1: given 3^p Restricted coins, set aside 3^(p-1) coins, and divide the others into two pans, in any pattern as long as number of H coins in each pan are equal, and number of L coins in each pan are equal (either number could be zero, it's ok)
 
Now weigh the two pans. If they balance, the bad coin is in one of the 3^(p -1) restricted coins that were set aside. According to induction hypothesis, it will take an additional p-1 weighings to find the bad coin.
If they don't balance, one side is heavier than the other. There are exactly 3^(p -1) coins that could cause that side to be heavy: the H coins in that pan, plus the L coins in the opposite pan. Thus, the bad coin is one of those 3^(p -1) coins, and once again it will take p-1 weighings to find the bad coin.

So in both cases, we have performed one weighing, and it will take p-1 more weighings. Therefore it will take p weighings to locate the bad coin out of 3^p Restricted coins. Induction step is proved.

 

  Hide contents

So imagine the function R(n), the number of Restricted coins from which the bad coin can be found in n weighings.
R(n) = 3^n

But we had to perform one weighing in order to make all these Restricted coins. Can't we learn something additional from that weighing? Yes! If they balance, then we could pursue additional coins.

I need to request an OP boon ("a boon, Sire!") :

  Reveal hidden contents

please allow me to have one additional coin that is known to be good. My justification is uniformity: at every level, we need a known Good coin, and we've already identified some. But the initial weighing could also benefit from 1 known good coin, and we don't have one. 

  Hide contents

Now consider U(n), the number of Unrestricted coins from which the bad coin can be found in n weighings.
Follow this strategy. Create 3^n Restricted coins by weighing 1 Good coin and 3^n Unrestricted coins in the two pans. If they don't balance, then you have identified 3^n Restricted coins, and it will take n more weighings to find it.
If they do balance, the remaining coins are Unrestricted coins, and we can perform the same algorithm, with one fewer weighings.
So U(n) = R(n-1) + U(n-1)
Recursively, this works out to 
U(n) = R(n-1) + R(n-2) + ... + R(1) + U(1). 

  Hide contents

U(1) is interesting (and perhaps open to debate). Notice that U(0) = 1. That is, if you're given 1 coin and you're told one coin is bad, you can identify it with zero weighings. 

How many can you distinguish with 1 weighing? If The Boon is granted, you can distinguish 2 Unrestricted coins in 1 weighing, as follows.

Place one coin in one pan , place the Known Good coin in the other pan, and set another coin aside. 
If they balance, the bad coin is the one that was set aside. If they don't, the bad coin is the one opposite the Good coin.
So, with this OP-granted boon, U(1) = 2.

 

  Hide contents

The first few values of U(n):
U(2) = R(1) + U(1) = 3 + 2 = 5
U(3) = R(2) + R(1) + U(1) = 9 + 3 + 2 = 14
U(4) = 27 + 9 + 3 + 2 = 41
U (5) = 81 + 27 + 9 + 3 + 2 = 122

 

Congratulations! Unfortunately, the answer changes if I grant you this boon, so request denied.

But no worries! You've still solved it. The only thing that changes...

Spoiler

... is that you must weigh one less gold coin in the first weighing instead. This means that

U(n) = R(n-1) + R(n-2) + ... + R(1) + U(1) - 1

But since U(1) = 2 = R(0) + 1, this works out very cleanly.

U(n) = R(n-1) + R(n-2) + ... + R(0)

And so the answer becomes the one you initially gave.

I'd also like to give my own explanation of the recursive step for "constrained" coins. Some may find it interesting and/or more intuitive.

Spoiler

Imagine that you've weighed some coins against each other and that the scale has tipped to one side.

Divide these coins into three groups. Then,

• Leave each coin in the first group on its original plate.
• Move each coin in the second group to the opposite plate.
• Take each coin in the third group off the scale.

Assuming you have a few authentic coins on reserve, you can add coins to either plate to make the numbers equal.

Then, activate the scale.

• If the fake was in the first group, the scale should tip in the same direction as before.
• If the fake was in the second group, the scale should tip in the opposite direction.
• If the fake was in the third group, the scale should balance.

If these three groups are roughly of equal size, it should cut down the number of suspects by a factor of three.

 

[heliosmusic]

Hm, that's a tough one. Reminds me of East of the Sun, West of the Moon. I'm gonna need to think about this one