8
$\begingroup$

I'm interested in sets of dice that can be used to determine who "goes first" (hence the name) in an $N$-player game; more generally, I want to determine a complete ordering of the players with a single roll of the dice, and have this ordering be random. Specifically, then, what's needed is an assignment of the labels $\{1,2,...,Nm\}$ to the faces of $N$ different $m$-sided dice, such that:

  1. No two faces share a label (so no ties can occur).
  2. When a face is chosen at random on each die, the rank-ordering of the dice based on the chosen faces is uniformly random across all permutations (so the rolls are fair).

For instance, if $N=2$ and $m=2$ (two coins, basically), then you can label the coins $\{1,4\}$ and $\{2,3\}$. A solution for $N=4$ and $m=12$ is sold here. For what values of $N$ and $m$ are there solutions?

A simple constraint on the minimum value of $m$ comes from the fact that we are choosing one of $N!$ possibilities on the basis of $m^N$ equiprobable rolls; certainly the former must divide the latter. So for $N=2,3,4,5,6,\dots$, necessarily $m \ge 2, 6, 6, 30, 30, \dots$. Is this minimum value always achievable?

  • 0
    In fact, you should be able to use the fairness condition to bound the search space even more: first of all, find out which of the $\binom{12}{6}$ different 2-die assignments are fair, then for each of the $\binom{24}{12}$ ways of assigning the 24 numbers to two pairs of dice, iterate over all of the fair assignments of the first twelve numbers to$A$and $B$, and all the fair assignments of the other twelve numbers to $C$ and $D$, testing just those combinations for global fairness.2012-06-27

3 Answers 3

4

For the N=4 case, m=6 is not sufficient. I exhaustively checked all possible 4d6 configurations and came up empty handed. That is why the GoFirst dice on my website are 4d12 (12-sided). I do not yet know if m=30 is sufficient for N=5 (much less N=6).

Geometrically, a 60-sided fair polyhedron exists and is aesthetically pleasing (q.v. Pentakis Dodecahedron) if that is what is needed. But trying to find a 5d30 is proving more than a typical computer can handle, much less a 5d60.

  • 0
    Thanks! You're the de facto expert on the subject, so I appreciate your weighing in.2012-07-05
0

What constraints are there on $m$, the number of sides of the dice? Once $N$ hits $7$ you need $7$ to divide $m$ and there are no regular polyhedra that can do that. If all the dice are the same, you need $m$ to be a multiple of $210$ if $N \ge 7$. Maybe it is better to use dice of different sizes. There are 14 sided polyhedra that look close to spherical. The truncated cube and truncated octahedron should be able to have the dimensions chosen to be fair. Then for $N=7$, roll $d14, d20, 2d6$ to get $10080$ possibilities. If the dice are colored or otherwise distinguishable, all the $m_1m_2 \ldots m_n$ rolls are distinguishable, so if $N! | m_1m_2 \ldots m_n$ you can certainly do what you want.

  • 0
    Apart from the nice regular (m=4,6,8,12,20) and Archimedean (m=24,30,48,60,96,120) polyhedra, there are several infinite families of fair shapes, such as the bipyramid (traditional for m=16), the trapezohedron (traditional for m=10), the prism and the antiprism (usually with added endcaps), which allow realization of practical dice for any m.2014-04-17
0

If we remove the restriction that dice must have equal numbers of faces, then for $N\!=3$, we have (at least) the following two possibilities, with one $6$-sided, one $3$-sided and one $4$-sided dice (a total of $13$ faces): $1,3,7,8,11,12\qquad2,9,10\qquad4,5,6,13$ $1,3,8,9,10,11\qquad2,7,12\qquad4,5,6,13$ Since there is no need for faces on any single dice to be distinct, these are equivalent to: $1,3,5,5,7,7\qquad2,6,6\qquad4,4,4,8$ $1,3,6,6,6,6\qquad2,5,7\qquad4,4,4,8$ respectively.

It seems likely that there are also solutions for $N\!=4$ with fewer (perhaps a lot fewer) than a total of $48$ faces.

  • 0
    Good point! There are, it turns out, three fair possibilities for $2-4-6$ dice, twelve for $3-4-6$, four for $4-4-6$, two for $4-5-6$, thirty-five for $4-6-6$, sixteen for $5-6-6$, and eleven for $6-6-6$. None of these can be extended to $N=4$, though.2013-01-03