Fog Creek Software
Discussion Board




Four weighings?

Here's another one:

We know you can find the counterfeit coin out of 12 with 3 weighings.  (I also ask whether you can do 13.)

How many coins can you handle with four weighings?  Same problem as before; you have N coins, one of which might be heavy or light (you don't know which).  Your task is to find the largest N, and how it's done.

Note: there's a general solution on the web.  No cheating.  :-)

Paul Brinkley
Thursday, January 03, 2002

Paul - After playing for a while yesterday with your 13-coin problem and thinking about this new one, (and not looking up the answer), (and inviting discussion), I will venture a guess:

w == # of weighings
s == possible states = 3^w
m == coins weighed each time = s div 6
n == number of coins = m * 3

or:

for 3 weighings (4 each time, 12 coins)
4 (13, 39)
5 (40, 120)
6 (121, 363)
7 (364, 1092) ...

Of course, if this is so, 13 won't work in 3 weighings.
Also - this doesn't work too well for w=1 so maybe there might be some missing generality here.

James M 'Mike' Donovan
Friday, January 04, 2002

Good guess.  In fact, you're right.  The encoding approach (weigh N coins on each side for all weighings, without letting the result of a weighing influence what you do later) kinda makes the problem quite transparent.  With the classic approach, where you DO let early weighings influence your later ones, there's an interesting argument as to why you can always test ((3^N)-3)/2 coins with N weighings.

According to the above formula, you can test 0 coins with 1 weighing, but common sense alone should illustrate why.

Paul Brinkley
Monday, January 07, 2002

*  Recent Topics

*  Fog Creek Home