I'm not so hot with proofs, but my solution goes like this:
1) Divide the
coins in two equal piles.
2) If there is a leftover coin, set it aside.
3) Weigh the two batches of coins.
4) If they're
identical, the coin you took out was the light one.
5) Otherwise, set the heavy batch of coins aside with any remainders, and enter the light pile into step (1) until your pile is a pile of one. That coin is the
false coin.
This should solve the problem in (
log_2 (n))
iterations at most. If there's something faster, I'm sure
Eos will think of it.
"Let's do the Time Warp again..."