<pre>
Q: How can you play Russian Roulette with each person having a 50/50
chance of losing?  Assume you only have one bullet and you may not take
the bullet out of the gun.  The gun has six chambers.  Also assume that
the players spin the cylinder before each turn.  The problem is to find
a sequence of turns which makes the game fair.


A: Calculate the accumulated probability of losing for each player and
whichever has the lower number takes the next turn.

If you ever end up with a position where both players have the same
accumulated probability, then flip a coin (you have to do this on the
first turn anyway, it's not clear that you'll ever have to do it
again).

Just to make it clear, the probability of losing which you're
calculating is the a priori probability that you will have lost at or
before that point in the game.  It is NOT conditioned on the
information that both players have survived up to that point.  You're
trying to make a game where, at the start, both players have a 1/2
chance of winning.

Specifically, write down a geometric sequence starting with 1/6 and
with each entry 5/6 of the previous entry.  Both players start with a
total of zero.  Player A goes first, and adds 1/6 to his/her total, so
that A now has 1/6 while B has 0.  On the next turn, since B's total is
less than A's, it's B's turn.  B now has 5/36.  Next turn is B's again,
B now has 5/36 + 25/216, which is greater than 1/6, so it's now A's
turn again . . .  Continue until one player is dead.

The opening sequence is:  ABBABAABBAABBAABBAABBABAABB . . .

Clearly, if the game lasts indefinitely, the sum of A's and B's numbers
will approach 1.  The only way this algorithm can fail is if one of the
two numbers ever exceeds 1/2 (else both numbers will approach 1/2 from
below).  This problem can only occur if the sum of the lesser of A's
and B's numbers and the next number on the list exceeds 1/2, which
would mean that more than half of the remaining probability is in the
next number on the list.  But each number on the list is equal to only
1/6 of the sum of all the numbers that follow it, so this can never
happen.

In fact, there are a bunch of sequences that will work.  You can relax
the rule so that, as long as there's no possibility of one player's
total exceeding 1/2, you flip a coin.  This actually appears to be the
general solution.  All solutions could be generated by this method.  In
fact, you'll flip a coin on the majority of the turns (around 2/3).

You can end up with a sequence where A goes once, B goes 5 times, A
goes 29 times, . . .
</pre>
