Log in

No account? Create an account

Previous Entry | Next Entry

Question for my LJ friends

You have twelve coins. One of them is counterfeit, and is either too light or too heavy (you don't know which). You have a balance scale. How do you determine which coin is the counterfeit with only three weighings?


Feb. 11th, 2007 05:00 am (UTC)
Re: not so simple, really
I only thought of one main solution method (I agree on the groups of four for the first step, and the need for lots of conditional statements). On one conditional branch, I see a couple options for how to do the second and third steps. The other conditional branch, twice as likely, seems to require a strict conditional choice of 2nd and 3rd weighings.

The n-coin question is interesting. I think a lower bound on the minimum number of weighings might be

Log (base 3) n

since each weighing, at best, divides the coins into three groups, and could hypothetically cut the number of suspect coins by a factor of three.

Feb. 11th, 2007 06:27 am (UTC)
Re: not so simple, really
Nice, I think that almost solves it.

One ambiguity involves whether you are required to determine whether the counterfeit coin is too heavy or too light. Requiring this rounds out the question. For instance, for the 12 coin case, I don't see any branches that could then lead to a solution in two steps.

Anyway, if you do this, then I think you can bump up the lower bound to floor(log (base 3) n + 1), where floor finds the next smallest integer.

So for three coins, you need two weighings, and this automatically implies (via tevarin's reasoning) that for nine coins you need 3 weighings and for 27 you need 4, etc.

Plus, it's pretty likely the function is non-decreasing, i.e. there's never a situation where if you add one more coin you can do it in fewer steps (which the exception of n=2, which is unsolvable!)

So that means the interesting part that's left can be re-phrased: for an integer n, what's the largest number of coins for which the problem can be solved in n weighings?

p.s. Hi thisgirliknow, thanks for starting this discussion. We like your dog name suggestion...I'd say it's a top contender.

Feb. 11th, 2007 01:41 pm (UTC)
Re: not so simple, really
Hi, Alan, fancy seeing you on LJ. Glad you like the name Lola.


Much like pineapples, I am hardcore.

Latest Month

March 2019


Powered by LiveJournal.com
Designed by yoksel