Fog Creek Software
Discussion Board

Thirteen coins in three weighings?

Okay, I'm bored, so I'll post a few coin balancing problems of my own:

In another thread, I mentioned that in the classic problem, there are 24 possibilities to distinguish: 12 coins, each of which might be heavy or light.

A balance scale is a ternary device; each time you use it, you can reduce the cases to 1/3, but no better, unless you get lucky.  The analog is the guessing game where you pick a number between 1 and 100, and I ask yes-no questions to find it.  A yes-no question is a binary device, and so I can find it in seven questions at worst, less if I get lucky (for instance, if my first question was "Is it greater than 99?" and you said "yes").

With three weighings, however, a ternary device should be able to distinguish between 27 cases, right?  (3 times 3 times 3...)  If you had 13 coins, you'd have 26 possible cases.  So here's the question:  can you find the counterfeit coin out of 13 coins, with three weighings?  If so, how?  If not, why not?

Paul Brinkley
Thursday, January 3, 2002

Yes, It is solvable, I assume u already know. (Ask if you don't)
But the original question holds 12 coins because it is much harder to solve 12 then 13.
Much more forks in the possible solutions.

Vladimir Sakharuk
Tuesday, April 15, 2003

*  Recent Topics

*  Fog Creek Home