?

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?

Comments

metahoss
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.



thisgirliknow
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.

Profile

botticelli
thisgirliknow
Much like pineapples, I am hardcore.

Latest Month

March 2019
S M T W T F S
     12
3456789
10111213141516
17181920212223
24252627282930
31      

Tags

Powered by LiveJournal.com
Designed by yoksel