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.
There is the possibility of "reusing" coin flips, if one is permitted to re-randomize. Each time you flip a coin, you record your result.
For example. Suppose N = 24.
You could do 3 flips each time dividing the group by 2.
Now you're down to 3 people. Whatever method you now use to pick one out of the three, you already have 3 coin flips that wlog you can apply to your algorithm for 3 people. Is this allowed? I think maybe, but only if the 3 are re-randomized.
It gets worse. Suppose after the first flip, you re-randomize the 12 who "passed" the first coin flip test. Just reuse the first coin flip to narrow it down to 6; re-randomize and reuse again and you are down from 24 to 3 people having only flipped the coin once. Is this allowed?
I tend to think this reuse of coin flips should not be allowed since the re-randomize step is in a sense equivalent to a coin flip.
??
Edited on July 2, 2024, 10:31 am
|
|
Posted by Larry
on 2024-07-02 10:26:29 |
A clarification before solving
