The following puzzle appeared (worded differently) in John Derbyshire's May diary .
Can you label the faces of 3 cubical dice with the numbers 1,2,3 ... 18 (using each number exactly once) so that if someone else picks any one of the three dice you can then pick another so that if you both roll your chosen dies with the high roller winning you will win more than half the time? How big an edge can you achieve by an appropriate labeling? Can you prove optimality?
Derbyshire follows up here .
They hold some quarter
4 hours ago
The three dice--call them p, r, and s (for paper, rock, and scissors)--must have the circular relationships p > r > s > p, where x > y indicates that, when die x is matched against die y, the probability w(x) that x wins is at least 1/2. If number n appears on die x, n+1 appears on y, and x > y, then exchanging the two numbers increases w(x) without altering the other two w(z)'s; so you need only consider arrangements such that, wherever two consecutive numbers appear on different dice x and y, where x > y, the larger number appears on x. Also, you may arbitrarily assign the largest number to die p. These restrictions significantly speed up a search by computer, which discovers the four solutions that maximize the least of the three w(z), its value ww being 21/36 = 0.5833. These solutions (separated by semicolons and with the numbers on each single die enclosed in parentheses) are as follows:
ReplyDelete(1, 6, 7, 8, 17, 18) (3, 4, 5, 14, 15, 16) (2, 9, 10, 11, 12, 13);
(3, 4, 5, 10, 17, 18) (1, 2, 9, 14, 15, 16) (6, 7, 8, 11, 12, 13);
(5, 6, 7, 8, 9, 18) (2, 3, 4, 15, 16, 17) (1, 10, 11, 12, 13, 14);
(1, 2, 11, 12, 13, 18) (6, 7, 8, 9, 10, 17) (3, 4, 5, 14, 15, 16).
The puzzle may be extended to treat "dice" having any number N of "sides", where N >= 2. The following lists ww in parentheses for each N <= 12. Note that ww for larger N hovers around 0.6, which suggests a new puzzle: What is the limiting behavior of ww as N -> infinity?
2 ( 2/ 4 = 0.500000)
3 ( 5/ 9 = 0.555556)
4 ( 9/ 16 = 0.562500)
5 (15/ 25 = 0.600000)
6 (21/ 36 = 0.583333)
7 (29/ 49 = 0.591837)
8 (39/ 64 = 0.609375)
9 (48/ 81 = 0.592593)
10 (60/100 = 0.600000)
11 (72/121 = 0.595041)
12 (88/144 = 0.611111)