Given a balance scale that is sure to break after X weighings, find an equation for the largest number of coins N, from which you can determine a fake coin that has the wrong weight if

A: You know whether the fake is lighter or heavier

B: You do not know whether the fake is lighter or heavier

(Assume only one of the N coins is fake)

(In reply to solution to B by pleasance)

4 coins are 'unsolvable' in 2 weighings because:

4 coin 'solutions' need eight pieces of info. So, any weighing strategy must lead to a decision tree with at least 8 terminal branches after two weighings.

The first weighing can either have one coin or two coins on each side

Scenario 1: (coin 1 vs coin 2)

If coin 1 > coin 2, then either coin 1 is 'fake' and heavy or coin 2 is 'fake' and light.

To determine the real 'fake' between them, at least one of the two 'initial' coins will have to be part of the second weighing. Also, just switching the coins from one side to the other will not do the trick, as won't just adding one 'standard' coin on each side.

So we have to either weight one of the 'initial' coins against a 'standard' coin, or weigh both 'initial' coins against both 'standard' coins. In either case the two sides cannot be balanced. Hence this branch of the decision tree can at most have two sub-branches.

If coin 1 < coin 2, then similarly this branch can also yield at most two sub-branches after the second weghing.

If coin 1 = coin 2, then we can at most have three sub-branches from this branch after the second weighing.

So, we can have at most 2+2+3 = 7 sub-branches after two weighings. This is not enough.

Scenario 2: Coin 1 + Coin 2 vs Coin 3 + Coin 4

Clearly the two sides cannot be balanced. Hence after 1 weighing we have two branches. Each branch can lead to at most three sub-branches.

So we can have at most 3 + 3 = 6 sub-branches after two weighing. This is also not enough.

Would love to see the 'solution' for either X=2,N=4 or X=3,N=13

Posted by Sanjay on 2003-05-18 10:12:28