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.
Before getting into an actual solution, here is an algorithmic trick idea which might help in special cases where two or multiple factors sum to a power of 2.
e.g. N = 15. 3*5=15 3+5=8
Number them from 0 to 14. Can be simultaneously 5 groups of 3, and/or 3 groups of 5.
Flip 3 times, converting the results in order to construct a 3 digit binary number.
If that number is 0,1,2,3,4 select the corresponding group of three.
If the binary is 5,6,7 select from the corresponding group of five: group {0,1,2} if the binary number is {5,6,7}.
This works for 15 because its prime factors add to a power of 2.
In 3 flips you've narrowed down from 15 to either 3 (5/8 chance) or 5 (3/8 chance). Log2 of 15 is about 3.9, so there may well be a better way making this trick obsolete:
Another thought for 15 is to add one to get a power of 2. Flip 4 times to make a binary number. There is a 15/16 chance you're done: match the number to the person. If you select the one who doesn't exist, repeat the four flips. Expected flips is 4(1 + 1/16 + 1/16^2 etc) = 4*16/15 = 4.2666...
I don't think I can narrow down from 3 to 1 or 5 to 1 in just 1.2666 flips, so for N=15, the "trick" didn't help. But I haven't ruled out that it might help for larger numbers, especially if it is more than two factors.
|
|
Posted by Larry
on 2024-07-02 11:11:10 |
an algorithmic trick idea
