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
re: current thoughts by Steve Herman)
Take a look at 63 vs 65, 2^k - 1 and 2^k + 1.
f(64) = 6
f(63) = 6.10 It's good to be just under a power of 2
f(21) + f(3) = 10.29 Factoring makes it worse
f(7) + f(9) = 10.54
f(7) + f(3) + f(3) = 8.76 best factoring but inflate better
f(65) = 13.78 It's bad to be just over a power of 2
f(13) + f(5) = 9.72 Factoring helps
Try overinflating for 65
7 * 128/(1*65) = 13.784615384615385 Standard inflate
8 * 256/(3*65) = 10.502564102564103
9 * 512/(7*65) = 10.127472527472527 <-- best overinflate
10*1024/(15*65) = 10.502564102564103
|
|
Posted by Larry
on 2024-07-02 22:58:29 |
look at 63 vs 65
