The “Prime Sided Dice” logic puzzle was all about simulating fair dice using other fair dice. In this puzzle, we limit ourselves even further and try to simulate a fair die using only coins.
Imagine you have k coins, which are not necessarily fair. You get to choose the bias for each of the coins. (i.e. You choose the probability that each coin comes up heads.) You may then use whatever procedure you like to simulate a fair n-sided die. You are allowed to flip the same coin more than once. The catch is that your procedure must end in some bounded number of coin flips.
For example, if you have a coin that comes up heads with probability 1/3, and another coin that comes up heads with probability 1/2, then you can simulate a 3-sided die by flipping the first coin, returning 1 if you get heads, and otherwise flipping the second coin and returning 2 or 3 depending on the result.
As a function of n, what is the minimum number k of coins that you need? (i.e. Which dice can be simulated with 1 coin? 2 coins? 3 coins? etc.)
The solution will eventually be posted in the comments. If you have been working on this puzzle for a while, and are starting to lose interest, please make sure you view this minor hint before you give up. I advise anyone who has been working on this puzzle for more than an hour to just view the hint. It is more interesting than it is helpful. (Written in rot13, decode here.)
Gurer rkvfgf na vagrtre x fhpu gung rirel qvr pna or fvzhyngrq hfvat ng zbfg x pbvaf.
For a given N we can use N-1 coins biased 1/N, 1/(N-1), …, 1/2. Rolling them in that order, we let the first occurrence of heads be our roll. For example
H = 1
TH = 2
TTH = 3
…
It is easy to see that the probability of rolling a k is 1/N. Let’s call this algorithm the “N-coin-flip”.
Let the prime factorization of N be
p_1^a_1 p_2^a^2 … p_k^a_k
where p_1 < p_2 < … < p_k. Then we only need p_k -1 coins with at most sum{(p_i – 1) a_i} coin flips. The algorithm goes as follows. Split N into p_1 intervals of length N/p_1. Then do a "p_1-coin-flip" to determine which interval to proceed and then repeat. For example, let N = 63 = 3^2 7
Split N into 3 intervals [1-21][22-42][43-63]
"3-coin-flip": TH = 2
Working interval [22-42]
Split further into 3 intervals [22-28][29-35][36-42]
"3-coin-flip": TT = 3
Working interval [36-42]
Split further into 7 intervals [36][37][38][39][40][41][42]
"7-coin-flip": TTTTH = 5
Roll = 40
This procedure works, but it is not optimal.
I can do 2log2(n) where log2 is the base two logarithm.
If n is even flip a fair coin and then the problem is reduced to n/2.
If n is odd flip a coin with P(heads)=(n-1)/2 and a coin with P(heads)=n/(n-1). You can use the results to partition n=2m+1 as (m,m,1) by using (H,TH,TT). Then the problem has been reduced to the problem for m=(n-1)/2.
Each step takes at most two flips and there are log2(n) steps. So we’re done in 2log2(n).
I can in fact do alog2(n)+C where a is arbitrarily close to 1 and C doesn’t depend on n.
It sounds like you are using a number of coins equal to the number of 1s in the binary expansion, since you are reusing your fair coin a lot, and you get one of the binary digits for free.
Wait, are we allowed to flip the same coin more than once?
(Sorry for spamming your comments thread)
Yes, you are.
Okay, in that case I have the following. (I got this before reading your hint)
a=1 pna or qbar jvgu ab pbvaf, pyrneyl bcgvzny. Gur cbjref bs gjb pna or qbar jvgu n fvatyr snve pbva, nyfb pyrneyl bcgvzny. Gur erfg bs gur ahzoref pna or qbar jvgu gjb pbvaf, naq guvf vf bcgvzny vs jr erfgevpg bhefryirf gb engvbany cebonovyvgvrf. V qba’g unir n unaqyr ba gur veengvbany cebonovyvgl pnfr lrg.
Gb qb gur gjb pbva pbafgehpgvba, gnxr n snve pbva naq n 1/a pbva. Syvc gur snve pbva z gvzrf jvgu 2^z>=(a-1)^2. Syvc gur 1/a pbva bapr. Gura gurer ner 2^(z+1) bhgpbzrf, unys unir cebonovyvgl 1/(a2^z) naq unys unir cebonovyvgl (a-1)/(a2^z). Jr jnag gb tebhc gurfr bhgpbzrf gbtrgure vagb cnepryf bs cebonovyvgl 2^z/(a2^z). Svyy gur cnepryf terrqvyl jvgu gur ynetre cebonovyvgl bhgpbzrf. Rnpu bar jvyy gnxr ng yrnfg a-1 fhpu bhgpbzrf, naq bapr vg vf shyy gur fcnpr erznvavat jvyy or e/(a2^z) jvgu e<(a-1), juvpu pna or svyyrq rknpgyl jvgu e bs gur yrff yvxryl bhgpbzrf. Fvapr e<a-1 jr jvyy eha bhg bs gur ynetre cebonovyvgl bhgpbzrf svefg, naq gur erfg pna or svyyrq ol gur fznyy cebonovyvgvrf.
Everything you say is correct. Well Done! However, you have not solved the puzzle yet, because you have to look at the case that you said you skipped.