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 Almost a monkey wrench by Jer)

I think that unless the N is of the form 2^a for integers a there is no way to guarantee the tossing eventually ends.

Posted by Steve Herman on 2024-07-04 09:03:47