Intransitive dice

From Wikipedia, the free encyclopedia
(Redirected from Non-Transitive Dice)
Jump to navigation Jump to search

Template:Short description Template:Multiple issues A set of dice is intransitive (or nontransitive) if it contains X>2 dice, X1, X2, and X3... with the property that X1 rolls higher than X2 more than half the time, and X2 rolls higher than X3 etc... more than half the time, but where it is not true that X1 rolls higher than Xn more than half the time. In other words, a set of dice is intransitive if the binary relation – Template:Math rolls a higher number than Template:Math more than half the time – on its elements is not transitive. More simply, X1 normally beats X2, X2 normally beats X3, but X1 does not normally beat Xn.

It is possible to find sets of dice with the even stronger property that, for each die in the set, there is another die that rolls a higher number than it more than half the time. This is different in that instead of only "A does not normally beat C" it is now "C normally beats A". Using such a set of dice, one can invent games which are biased in ways that people unused to intransitive dice might not expect (see Example).[1][2][3][4]

Example

File:Intransitive dice 2.svg
An example of intransitive dice (opposite sides have the same value as those shown).

Consider the following set of dice.

  • Die A has sides 2, 2, 4, 4, 9, 9.
  • Die B has sides 1, 1, 6, 6, 8, 8.
  • Die C has sides 3, 3, 5, 5, 7, 7.

The probability that A rolls a higher number than B, the probability that B rolls higher than C, and the probability that C rolls higher than A are all Template:Sfrac, so this set of dice is intransitive. In fact, it has the even stronger property that, for each die in the set, there is another die that rolls a higher number than it more than half the time.

Now, consider the following game, which is played with a set of dice.

  1. The first player chooses a die from the set.
  2. The second player chooses one die from the remaining dice.
  3. Both players roll their die; the player who rolls the higher number wins.

If this game is played with a transitive set of dice, it is either fair or biased in favor of the first player, because the first player can always find a die that will not be beaten by any other dice more than half the time. If it is played with the set of dice described above, however, the game is biased in favor of the second player, because the second player can always find a die that will beat the first player's die with probability Template:Sfrac. The following tables show all possible outcomes for all three pairs of dice.

Player 1 chooses die A
Player 2 chooses die C		 Player 1 chooses die B
Player 2 chooses die A		 Player 1 chooses die C
Player 2 chooses die B
Template:Diagonal split header 2 4 9 Template:Diagonal split header 1 6 8 Template:Diagonal split header 3 5 7
3 C A A 2 A B B 1 C C C
5 C C A 4 A B B 6 B B C
7 C C A 9 A A A 8 B B B

If one allows weighted dice, i.e., with unequal probability weights for each side, then alternative sets of three dice can achieve even larger probabilities than 59≈0.56 that each die beats the next one in the cycle. The largest possible probability is one over the golden ratio, 1φ≈0.62.[5]

Variations

Efron's dice

Efron's dice are a set of four intransitive dice invented by Bradley Efron.[4]

File:Efron dice 2.svg
Representation of Efron's dice. The back side of each die has the same faces as the front except for the 5, 5, 1 die (where the back side of 5 is 1, and the back side of 1 is 5).

The four dice A, B, C, D have the following numbers on their six faces:

  • A: 4, 4, 4, 4, 0, 0
  • B: 3, 3, 3, 3, 3, 3
  • C: 6, 6, 2, 2, 2, 2
  • D: 5, 5, 5, 1, 1, 1

Each die is beaten by the previous die in the list with wraparound, with probability Template:Sfrac. C beats A with probability Template:Sfrac, and B and D have equal chances of beating the other.[4] If each player has one set of Efron's dice, there is a continuum of optimal strategies for one player, in which they choose their die with the following probabilities, where 0 ≤ x ≤ Template:Sfrac:[4]

P(choose A) = x
P(choose B) = Template:Sfrac - Template:Sfracx
P(choose C) = x
P(choose D) = Template:Sfrac - Template:Sfracx

Miwin's dice

File:Miwin Wuerfel Titan.gif
Miwin's dice

Script error: No such module "Labelled list hatnote". Miwin's Dice were invented in 1975 by the physicist Michael Winkelmann.

Consider a set of three dice, III, IV and V such that

  • die III has sides 1, 2, 5, 6, 7, 9
  • die IV has sides 1, 3, 4, 5, 8, 9
  • die V has sides 2, 3, 4, 6, 7, 8

Then:

Intransitive dice set for more than two players

A number of people have introduced variations of intransitive dice where one can compete against more than one opponent.

Three players

Oskar dice

Oskar van Deventer introduced a set of seven dice (all faces with probability Template:Sfrac) as follows:[6]

  • A: 2, 2, 14, 14, 17, 17
  • B: 7, 7, 10, 10, 16, 16
  • C: 5, 5, 13, 13, 15, 15
  • D: 3, 3, 9, 9, 21, 21
  • E: 1, 1, 12, 12, 20, 20
  • F: 6, 6, 8, 8, 19, 19
  • G: 4, 4, 11, 11, 18, 18

One can verify that A beats {B,C,E}; B beats {C,D,F}; C beats {D,E,G}; D beats {A,E,F}; E beats {B,F,G}; F beats {A,C,G}; G beats {A,B,D}. Consequently, for arbitrarily chosen two dice there is a third one that beats both of them. Namely,

  • G beats {A,B}; F beats {A,C}; G beats {A,D}; D beats {A,E}; D beats {A,F}; F beats {A,G};
  • A beats {B,C}; G beats {B,D}; A beats {B,E}; E beats {B,F}; E beats {B,G};
  • B beats {C,D}; A beats {C,E}; B beats {C,F}; F beats {C,G};
  • C beats {D,E}; B beats {D,F}; C beats {D,G};
  • D beats {E,F}; C beats {E,G};
  • E beats {F,G}.

Whatever the two opponents choose, the third player will find one of the remaining dice that beats both opponents' dice.

Grime dice

Dr. James Grime discovered a set of five dice as follows:[7][8]

  • A: 2, 2, 2, 7, 7, 7
  • B: 1, 1, 6, 6, 6, 6
  • C: 0, 5, 5, 5, 5, 5
  • D: 4, 4, 4, 4, 4, 9
  • E: 3, 3, 3, 3, 8, 8

One can verify that, when the game is played with one set of Grime dice:

  • A beats B beats C beats D beats E beats A (first chain);
  • A beats C beats E beats B beats D beats A (second chain).

However, when the game is played with two such sets, then the first chain remains the same, except that D beats C, but the second chain is reversed (i.e. A beats D beats B beats E beats C beats A). Consequently, whatever dice the two opponents choose, the third player can always find one of the remaining dice that beats them both (as long as the player is then allowed to choose between the one-die option and the two-die option):

Sets chosen
by opponents 		Winning set of dice
Type Number
A B E 1
A C E 2
A D C 2
A E D 1
B C A 1
B D A 2
B E D 2
C D B 1
C E B 2
D E C 1

Four players

It has been proved that a four player set would require at least 19 dice.[7][9] In July 2024 GitHub user NGeorgescu published a set of 23 eleven sided dice which satisfy the constraints of the four player intransitive dice problem.[10] The set has not been published in an academic journal or been peer-reviewed.

Four players

A four-player set is proved to require at least 19 dice.[7][11]

Georgescu dice

In 2024, American scientist Nicholas S. Georgescu discovered a set of 23 dice which solve the four-player intransitive dice problem.[12]

File:23-dice plot.png
Four-player intransitive dice win graph
0 40 61 83 105 116 158 173 203 213 234
1 29 46 89 109 119 153 175 196 226 243
2 41 54 72 113 122 148 177 189 216 252
3 30 62 78 94 125 143 179 205 229 238
4 42 47 84 98 128 138 181 198 219 247
5 31 55 90 102 131 156 183 191 209 233
6 43 63 73 106 134 151 162 184 222 242
7 32 48 79 110 137 146 164 200 212 251
8 44 56 85 114 117 141 166 193 225 237
9 33 64 91 95 120 159 168 186 215 246
10 45 49 74 99 123 154 170 202 228 232
11 34 57 80 103 126 149 172 195 218 241
12 23 65 86 107 129 144 174 188 208 250
13 35 50 69 111 132 139 176 204 221 236
14 24 58 75 92 135 157 178 197 211 245
15 36 66 81 96 115 152 180 190 224 231
16 25 51 87 100 118 147 182 206 214 240
17 37 59 70 104 121 142 161 199 227 249
18 26 67 76 108 124 160 163 192 217 235
19 38 52 82 112 127 155 165 185 207 244
20 27 60 88 93 130 150 167 201 220 230
21 39 68 71 97 133 145 169 194 210 239
22 28 53 77 101 136 140 171 187 223 248

Li dice

Youhua Li subsequently developed a set of 19 dice with 171 faces each that solves the four-player problem. This has been shown to be extensible for any number of dice given a domination graph with n nodes, producing dice with n(n−1)/2 faces.[13]

Intransitive 12-sided dice

In analogy to the intransitive six-sided dice, there are also dodecahedra which serve as intransitive twelve-sided dice. The points on each of the dice result in the sum of 114. There are no repetitive numbers on each of the dodecahedra.

Miwin's dodecahedra (set 1) win cyclically against each other in a ratio of 35:34.

The miwin's dodecahedra (set 2) win cyclically against each other in a ratio of 71:67.

Set 1:

D III purple 1 2 5 6 7 9 10 11 14 15 16 18
D IV red 1 3 4 5 8 9 10 12 13 14 17 18
D V dark grey 2 3 4 6 7 8 11 12 13 15 16 17

Set 2:

D VI cyan 1 2 3 4 9 10 11 12 13 14 17 18
D VII pear green 1 2 5 6 7 8 9 10 15 16 17 18
D VIII light grey 3 4 5 6 7 8 11 12 13 14 15 16

Intransitive prime-numbered 12-sided dice

It is also possible to construct sets of intransitive dodecahedra such that there are no repeated numbers and all numbers are primes. Miwin's intransitive prime-numbered dodecahedra win cyclically against each other in a ratio of 35:34.

Set 1: The numbers add up to 564.

PD 11 grey to blue 13 17 29 31 37 43 47 53 67 71 73 83
PD 12 grey to red 13 19 23 29 41 43 47 59 61 67 79 83
PD 13 grey to green 17 19 23 31 37 41 53 59 61 71 73 79

Set 2: The numbers add up to 468.

PD 1 olive to blue 7 11 19 23 29 37 43 47 53 61 67 71
PD 2 teal to red 7 13 17 19 31 37 41 43 59 61 67 73
PD 3 purple to green 11 13 17 23 29 31 41 47 53 59 71 73

Generalized Muñoz-Perera's intransitive dice

A generalization of sets of intransitive dice with N faces is possible.[14] Given N≥3, we define the set of dice {Dn}n=1N as the random variables taking values each in the set {vn,j}j=1J with

ℙ[Dn=vn,j]=1J,

so we have N fair dice of J faces.

To obtain a set of intransitive dice is enough to set the values vn,j for n,j=1,2,…,N with the expression

vn,j=(j−1)N+(n−j)mod(N)+1,

obtaining a set of N fair dice of N faces

Using this expression, it can be verified that

ℙ[Dm<Dn]=12+12N−(n−m)mod(N)N2,

So each die beats ⌊N/2−1⌋ dice in the set.

Examples

3 faces

D1 1 6 8
D2 2 4 9
D3 3 5 7

The set of dice obtained in this case is equivalent to the first example on this page, but removing repeated faces. It can be verified that D3>D2,D2>D1 and D1>D3.

4 faces

D1 1 8 11 14
D2 2 5 12 15
D3 3 6 9 16
D4 4 7 10 13

Again it can be verified that D4>D3,D3>D2,D2>D1 and D1>D4.

6 faces

D1 1 12 17 22 27 32
D2 2 7 18 23 28 33
D3 3 8 13 24 29 34
D4 4 9 14 19 30 35
D5 5 10 15 20 25 36
D6 6 11 16 21 26 31

Again D6>D5,D5>D4,D4>D3,D3>D2,D2>D1 and D1>D6. Moreover D6>{D5,D4},D5>{D4,D3},D4>{D3,D2},D3>{D2,D1},D2>{D1,D6} and D1>{D6,D5}.

See also

References

Template:Reflist

Sources

Template:Refbegin

  • Script error: No such module "citation/CS1".Template:ISBN needed
  • Script error: No such module "citation/CS1".

Template:Refend

External links

  1. ↑ Script error: No such module "citation/CS1".
  2. ↑ Script error: No such module "citation/CS1".
  3. ↑ Script error: No such module "Citation/CS1".
  4. ↑ a b c d Script error: No such module "Citation/CS1".
  5. ↑ Script error: No such module "Citation/CS1".
  6. ↑ Script error: No such module "citation/CS1".
  7. ↑ a b c Script error: No such module "citation/CS1".
  8. ↑ Script error: No such module "Citation/CS1".
  9. ↑ Script error: No such module "Citation/CS1".
  10. ↑ Script error: No such module "citation/CS1".
  11. ↑ Script error: No such module "Citation/CS1".
  12. ↑ Script error: No such module "citation/CS1".
  13. ↑ Script error: No such module "citation/CS1".
  14. ↑ Script error: No such module "citation/CS1".
Retrieved from "http://debianws.lexgopc.com/wiki143/index.php?title=Intransitive_dice&oldid=2659947"