```Author: jason (Jason Jordan)
Date: 2003-Oct-18 06:50:28

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.

Author: bandsmer (Michael Bandsmer)
Date: 2003-Oct-20 05:27:33

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

Author: jason (Jason Jordan)
Date: 2003-Oct-20 05:38:02

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.

Author: tomc (Tom Carmichael)
Date: 2003-Oct-20 13:59:29

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.  :-)
```