“You have N ≥ 2 identical-looking coins”

If N = 2, one will be light and one heavy, but you won’t know which is fake.

So isn’t the statement as follows “What is the smallest number of weighings you need in order to figure out whether the fake coin is lighter or heavier?” a loaded question?

Although if you think about it, if they are identical in looks and must be placed on a balance scale like, then they probably look and feel the same, and if they feel the same, they are probably made out of the same material, in which case, the heavier coin would be worth more, in terms of material. A skilled metal worker would be able to extract the excess metal out of the coin, and leave the remaining coin looking untouched, in which case, you now have a coin AND a small chunk of metal alloy, however, if you don’t do the metal work, or if it’s not done for free, it’s probably gonna cost more than any of today’s legal tender in coins, or two of them for that matter. Unless it is an antique coin, in which case, if the fake one is a modern replica, I wouldn’t care much for it, however if it’s an ancient duplicate of the coin from its time, that would be pretty cool.

Long story short, N > 2.

]]>Brilliant.

]]>For problem 3: if M = 2^x -1, a single weighing is enough (given enough coins, N >= M).

M=3: Place scale 2 (plus 1 coin) and scale 3 on different sides of scale 1. Place 1 coin on 1 side of scale 2, and 1 coin on one side of scale 3.

M=7: As above; but place scale 4 (plus 1 coin) and 5 on opposing sides of scale 2, and scale 6 (plus 1 coin) and 7 on opposing sides of scale 3.

etc.

]]>If M=3 or N is odd you need 1 extra weighing (in the first case because you don’t know which half of the coins contains the fake one, in the second case because in the worst case your first weighing results in equal weight, and then you still need at least M-1 weighings for M scales.

For M=2 it’s a little bit trickier and depends on the exact number of coins.

]]>