n coins. Which is fake? [duplicate]

This question already has answers here: Closed 12 years ago.

Possible Duplicate:

Algorithm to find minimum number of weighings required to find defective ball from a se开发者_开发技巧t of n balls

We have n coins. One of them is fake, which is heavier or lighter (we don't know). We have scales with 2 plates. How can we get the fake coin in p moves?

Can you give me a hand for writing such a program? No need a whole program, just ideas.

Thank you.

---

This is known as Balance puzzle. See Marcel Kołodziejczyk’s Two-pan balance and generalized counterfeit coin problem for a generalization of this problem.

---

I remember solving this for n=12 and 13, partly by hand and then with a program at the end. I don't know how I would solve it for a general n... but I know how I'd start - by considering small values of n and doing it by hand.

I suspect there are essentially patterns that can be used recursively for this... but you'll find them much easier to discover with pen and paper for small values (n=4 to 7, for example) than by coding.

---

Put coins on each side, the real ones will balance each other out, the fake will make the scale go either way. When the scales aren't balanced, one of the 2 you just put on is fake, try each against a real coin.

If the coins are objects you're handed, then you should be able to do that in a program quite easily.