the fake coin problem

You are given n gold coins, and one of them is fake. Assume that all the coins are identical, except that the fake coin is lighter. Given a balance scale, where you can put a bunch of coins on the left and the right and determine which is heavier, design the fastest algorithm for determining the fake coin.

Prove that no algorithm can be faster that yours.

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..."

1) Divide the coins into three piles as equally as possible
2) Measure two of the piles that have the same number of coins (i.e., if all three have the same number, any two. If there is one left over, measure the two that don't get it. If there are two left over, measure the two that get them.)
3) If the two you measured are identical, the light coin is out in the non-measured group. Otherwise, it's in the lighter group.
4) Repeat the previous steps with the offending pile
Should be faster.
Don't know how to prove it's the fastest, though.

the other, (harder) variant on this problem is if you know that the fake coin has a different weight than the others, but not if it's heavier or lighter...

Incidentally, the first time I heard this problem (or a variant) was in Piers Anthony's "With a Tangled Skein", when the protagonist has to pick out the good soul from a bunch of demons, using some sort of "good-vs-evil" balance, in only two weighings. (I think it was in Skein, anyway; it was definitely in one of the Incarnations of Immortality books. Actually, I am really unsure of the details, so if anyone wants to correct me, please do.)

The next time I heard it was while doing an internship at Microsoft; apparently it's a popular puzzle to ask during interviews out there..