Possible Duplicate:
Algorithm to find minimum number of weighings required to find defective ball from a set 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.
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.
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.
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.