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.
If N is slightly less than a power of 2 add enough imaginary people to inflate it to a power of 2. So N = 2^k - d. Add "d" imaginary friends.
Flip k times to form a k-digit binary number. Match that number to the person with the same number, or repeat k flips until you do.
Expected flips is k(1 + a + a^2 + ... ) where a = 2^k / (2^k - d)
= k*2^k/(2^k - d).
|
|
Posted by Larry
on 2024-07-02 11:44:09 |
"Inflate and Gamble" algorithm
