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
This should solve the problem in (log
_2 (n)) iteration
s at most. If there's something faster, I'm sure Eos
will think of it."Let's do the Time Warp again..."