This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.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?

probability/transitivity.s

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'

Clearly x+x' = y+y' = 1.

Prob. that A beats B = x' B beats C = x + x'y' C beats A = y

Therefore x' = y = x + x'y'

Solving for these gives x = y' = 1-y, x' = y = (-1 + sqrt(5))/2 = prob.

of each die beating the next = 0.618...

For four dice one obtains the probabilities:

B C D A B C D x y z 1 x' y' z'

A beats B: x'

B beats C: x + x'y'

C beats D: y + y'z'

D beats A: z

CONJECTURE: for any number of dice, at the optimum, the sequence of

probabilities abc...z1a'b'c...z' is palindromic.

We thus have the equalities:

x+x' = 1 y+y' = 1 z+z' = 1 x' = z = x + x'y' = x + x'y' y = y' (hence both = 1/2)

Solving this gives x = 1/3, z = 2/3 = prob. of each die beating the next.

Since all the numbers are rational, the limit is attainable with

finitely many equiprobable faces. E.g. A has one face, marked 0. C has

two faces, marked 2 and -2. B has three faces, marked 3, -1, -1. D has

three faces, marked 1, 1, -3. Or all four dice can be given six faces,

marked with numbers in the range 0 to 6.

Finding the solution for 5, 6, or n dice is left as an exercise.

-- ____ Richard Kennaway __\_ / School of Information Systems Internet: jrk@sys.uea.ac.uk \ X/ University of East Anglia uucp: ...mcsun!ukc!uea-sys!jrk \/ Norwich NR4 7TJ, U.K.

Martin Gardner (of course!) wrote about notransitive dice, see the Oct '74

issue of Scientific American, or his book "Wheels, Life and Other Mathematical

Amusements", ISBN 0-7167-1588-0 or ISBN 0-7167-1589-9 (paperback).

In the book, Gardner cites Bradley Efron of Stanford U. as stating that

the maximum number for three dice is approx .618, requiring dice with more

than six sides. He also mentions that .75 is the limit approached as the

number of dice increases. The book shows three sets of 6-sided dice, where

each set has 2/3 as the advantage probability.

Continue to: