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.
Solutions using the fewest coin tosses are preferred.
Does this mean the solution with the fewest expected number or the fewest guaranteed number?
The solutions people came up with are pretty cool but are based on trying to minimize the expected value. There is no limit to how many tosses may be required, hence the "Gamble"
Unless the N is of the form 2^a*3^b for integers a,b there is no way to guarantee the tossing eventually ends.
Even for N=5 there needs to be some rerolling (perhaps pretend N=6 and retry if the 6th possibility occurs.)
So although the problem was vague, there's only one way to solve it.
|
|
Posted by Jer
on 2024-07-03 17:14:35 |
Almost a monkey wrench
