Suppose you have one fair coin, that is, a coin that comes up heads half the time and tails half the time.
Show how to use this coin to choose fairly among N people. Solutions using the fewest coin tosses are preferred.
Wow! I am blown away by Paul's refinement to the "inflate and Gamble" approach. I don't think it would have occurred to me.
Here is a less brilliant refinement.
Say that N = 6.
Number the 6, using binary, as 000,001,010,011,100 and 101.
Using straight "inflate and gamble", you would flip 3 coins, succeed 3/4 of the time and reflip 1/4 of the time.
Expected flips = 3*(4/3) = 4
Instead, flip just twice. Let heads = 1. If they are both heads, than you have not succeeded, but you have only taken two flips to realize it.
Start over again. If one or both of them is not heads, then flip one more coin and you have randomly selected 1 of the 6 people.
Expected flips = 2*(4/3) + 1 = 3 + 2/3, which is an improvement.
This will not help if N = 2^k or 2^k - 1, but this approach does improve on straight "inflate and gamble" for any other N.
It may or may not be better than Paul's refinement for certain N. Also, for some N, Paul's refinement could benefit from this refinement.
This is certainly not a simple problem. Or if it is, I don't see it yet.
A different "Inflate and Gamble" refinement
