?

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. 10th, 2007 10:11 pm (UTC)
not so simple, really
I can only think of one solution to this, and it has lots of conditional statements. If you drew it as a flowchart, it would have several forks. I'm curious to know if there's a simpler one. My first step: divide your coins into sets of four...

A harder question: the same setup with n coins. Can you describe the minimum number of weighings needed as a function of n? You can always do it in n-1 or less, by comparing the coins one by one.
tevarin
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.

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