Back
The previous coin problem reminded me of an interesting puzzle I solved
back in college as part of a semester-long contest:
Call a biased coin a p-coin (0 <= p <= 1) if it comes up heads with
probability p and tails with probability 1 - p. We say that p simulates q
if by flipping a p-coin repeatedly (some finite number of times) one can
simulate the behavior of a q-coin. More precisely: There exists a positive
integer n and some subset of the 2^n possible outcomes of flipping the
p-coin n times such that the probability of a sequence of n flips being in
the subset is q.
For example, a 1/4-coin can be used to simulate a 5/8-coin by using 2 flips
and defining a pseudo-head to be either of the sequences HH or TT. The
probability of a pseudo-head is then 1/16 + 9/16 = 5/8.
Find one coin that can simulate both a 1/2-coin and a 1/3-coin.
This problem is a lot harder than I expected. I had to do quite a bit of
analysis to convince myself there is no rational p which works, and even
then, it took a lot of trial and error to come up with an irrational p that
works. The solution I found is
p = 1/2 + sqrt(6)/6 = 0.9082482906... = probability of head
So the probability of a tail is
1-p = 1/2 - sqrt(6)/6
Using this value for p, a 1/3-coin can be simulated by tossing the p-coin 5
times, with a pseudo-head sequence being any of the following:
- exactly 1 tail - probability 5*p^4*(1-p)
- HHHTT, HHTHT, HHTTH - probability 3*p^3*(1-p)^2
- TTTHH, TTHTH, TTHHT - probability 3*p^2*(1-p)^3
- exactly 1 head - probability 5*p *(1-p)^4
---------------------------------------------------
total probability 1/3
A 1/2-coin can be simulated by tossing the p-coin 8 times, with a
pseudo-head sequence being any of the following:
- exactly 1 tail - probability 8*p^7*(1-p)
- HHHHHHTT, HHHHHTHT, HHHHTHHT
or any rotation of these - probability 24*p^6*(1-p)^2
- HHHHHTTT, HHHHTHTT, HHHTHHTT
or any rotation of these - probability 24*p^5*(1-p)^3
- HHHHTTTT, HHHTHTTT
or any rotation of these - probability 16*p^4*(1-p)^4
- TTTTTHHH, TTTTHTHH, TTTHTTHH
or any rotation of these - probability 24*p^3*(1-p)^5
- TTTTTTHH, TTTTTHTH, TTTTHTTH
or any rotation of these - probability 24*p^2*(1-p)^6
- exactly 1 head - probability 8*p *(1-p)^7
------------------------------------------------------------
total probability 1/2
I verified these sums with a program that does symbolic math. Other
combinations of sequences for this value of p are possible as well.
However, I'm pretty sure the solution above uses the fewest number of coin
tosses (for this p anyway).
I'm still puzzled as to why p = 1/2 + sqrt(6)/6 happens to work, and why
everything else I tried doesn't. Is this the only solution? If so, how
can it be proven? If not, what other solutions are there?
In any case, I found it a very intriguing problem! Thanks!
Mike
Nice work! You found a solution different than the one I found, something
I did not expect. For some reason, I assumed that the solution was unique.
I haven't double-checked your numbers myself, but given your posts here, I
trust that your work is thorough. :-)
My solution used p = 1/2 + sqrt(12)/12. To simulate a 1/3-coin, flip this
coin twice. Call it a pseudo-head if the sequence is HT or TH; call it a
pseudo-tail otherwise. To simulate a 1/2-coin, flip this coin thrice.
Call it a pseudo-head if the sequence is HHH or TTT; call it a pseudo-tail
otherwise. I leave the math to the reader.
I remember coming up with it during a frenzied pen-and-notebook session
just before the problem deadline. But I can't recall how I went about
solving it. :-)
Note: This problem is from the paper "Versatile Coins" by Istvan Szalkai
and Dan Vellerman, American Mathematical Monthly 100 (1993) pp. 26--33.
I have not read it, just passing the info along.
It's interesting to me that both solutions have 1/sqrt(x) in the solution,
where x is a multiple a*b, given target pseudo coins 1/a and 1/b. I wonder
if that's a general case. In other words, is .5 +/- 1/sqrt(24) a solution?
How about if the targets are 1/3 and 1/5, is an answer .5 +/- 1/sqrt(15)?
Too many problems, not enough time. :-)