[seqfan] On simulating dice by coins
Jens Voß
jens at voss-ahrensburg.de
Sun Dec 21 22:26:40 CET 2014
If you have looked at the October, November and December riddles of
Michael Brand's site "Using your Head is Permitted"
(http://www.brand.site.co.il/riddles/usingyourhead.html), you are aware
of the question about how a fair n-sided die D_n can be simulated by a
finite number of throws with a (possibly biased) coin C_p which will
show "heads" with a probability p € [0,1].
The solution of the November riddle shows that this is possible for all
n, so for a given n, I would like to find the smallest number k such
there exists a C_p such that D_n can be simulated by k throws of C_p.
Obviously, if n = 2^k, then k throws of a fair coin can simulate a D_n,
and there is no way of doing so with fewer throws, so for powers of 2,
the problem is trivial.
For other n, the November riddle solution shows that p is necessarily
irrational, and k is bounded by the smallest number j such that n *
sum(i=0..k, binomial(j,i) mod (n-1) ) < 2^n, a sequence that I recently
submitted as http://oeis.org/A251738.
My feeling is that it is very likely that, for n not a power of 2,
A251738(n) is in fact equal to the smallest k for which a C_p simulates
a D_n, but that a proof would be quite difficult - just try it out for n=3!
Does anyone know of any results that could yield a proof for my hypothesis?
Best regards,
Jens
More information about the SeqFan
mailing list