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.
(In reply to
A different "Inflate and Gamble" refinement by Steve Herman)
A more complicated example of my refinement.
Let N = 9.
Then 4/16 of the time you start with 11 and know after 2 flips that you have failed.
2/16 of the time you start with 101 and know after 3 flips that you have failed.
1/16 of the time you flip 1001, and only know after 4 flips that you have failed.
Probability of success = 9/16.
Average flips if failing = (4*2 + 2*3 + 1*4)/7 = 18/7
Average flips while failing = (18/7)*(16/9 - 1) = 18/9 = 2
Average total flips = Flips while failing + flips after last failure =
2 + 4 = 6
If I have not made a mistake, then this is better than Paul's refinement for N = 9, and also better than the straight "Inflate + Gamble".
I know that this refinement, namely "inflate" and stop flipping as soon as you know that you have failed, is always at least as good as straight "inflate and gamble". I am not claiming that it is always at least as good as Paul's refinement.
A more complicated approach to N = 9
