This article is from the Puzzles FAQ, by Chris Cole firstname.lastname@example.org and Matthew Daly email@example.com with numerous contributions by others.
Can you number dice so that die A beats die B beats die C beats die A?
What is the largest probability p with which each event can occur?
Yes. The actual values on the dice faces don't matter, only their
ordering. WLOG we may assume that no two faces of the same or
different dice are equal. We can assume "generalised dice", where the
faces need not be equally probable. These can be approximated by dice
with equi-probable faces by having enough faces and marking some of
them the same.
Take the case of three dice, called A, B, and C. Picture the different
values on the faces of the A die. Suppose there are three:
A A A
The values on the B die must lie in between those of the A die:
B A B A B A B
With three different A values, we need only four different B values.
Similarly, the C values must lie in between these:
C B C A C B C A C B C A C B C
Assume we want A to beat B, B to beat C, and C to beat A. Then the above
scheme for the ordering of values can be simplified to:
B C A B C A B C A B C
since for example, the first C in the previous arrangement can be moved
to the second with the effect that the probability that B beats C is
increased, and the probabilities that C beats A or A beats B are
unchanged. Similarly for the other omitted faces.
In general we obtain for n dice A...Z the arrangement
B ... Z A B ... Z ...... A B ... Z
where there are k complete cycles of B..ZA followed by B...Z. k must be
at least 1.
CONJECTURE: The optimum can be obtained for k=1.
So the arrangement of face values is B ... Z A B ... Z. For three dice
it is BCABC. Thus one die has just one face, all the other dice have two
(with in general different probabilities).
CONJECTURE: At the optimum, the probabilities that each die beats the
next can be equal.
Now put probabilities into the BCABC arrangement:
B C A B C x y 1 x' y'
Prob. that A beats B = x' B beats C = x + x'y' C beats A = y
B C D A B C D x y z 1 x' y' z'
x+x' = 1 y+y' = 1 z+z' = 1 x' = z = x + x'y' = x + x'y' y = y' (hence both = 1/2)
-- ____ Richard Kennaway __\_ / School of Information Systems Internet: firstname.lastname@example.org \ X/ University of East Anglia uucp: ...mcsun!ukc!uea-sys!jrk \/ Norwich NR4 7TJ, U.K.