No account? Create an account

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. 9th, 2007 10:33 pm (UTC)
We did the same exercise in Kung Fu for logic training. I don't remember the solution, but I remember it helped to first do it with 11 coins. (We used billiard balls)
(Anonymous)
Feb. 10th, 2007 01:46 pm (UTC)
um, if they are all the same coin than I would think the solution would be rather easy.... Feb. 10th, 2007 03:02 pm (UTC)
one is cointerfeit 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. 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 '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 , 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. Feb. 12th, 2007 04:07 am (UTC)
I would weigh them in my hands first and then test. Feb. 12th, 2007 07:15 pm (UTC)
that's a great idea... find the one by weighing in hands that feels lighter or heavier. Then you weigh that coin, and two other coins, to make sure that it's different from the rest. 3 weighings. Feb. 12th, 2007 07:19 pm (UTC)
what if its a very small difference, unable to be detected by human hands? I mean, these are coins here.  