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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ I was just about to post the link to the Harshbarger dice when I saw that you had noted that in your question! For clarification, do you want your dice set to also have the property that the winner is equiprobable for sets of $n$ dice, $2\leq n\lt N$? (In other words, do you want a set that will work for any number of players up to $N$, or just a set that works for $N$ players exactly?) $\endgroup$ – Steven Stadnicki Jun 27 '12 at 19:22
  • 1
    $\begingroup$ @StevenStadnicki: If you have a version that works for $N$, doesn't it work for any less? Just ignore the players that aren't there in the order. $\endgroup$ – Ross Millikan Jun 27 '12 at 20:05
  • $\begingroup$ @RossMillikan Ahh, of course! The 'works for any $n\leq N$' thing was played up on the linked page so I thought it would be an extra constraint, but thinking about it it's just a projection operation on your permutation set, so it keeps equiprobability... $\endgroup$ – Steven Stadnicki Jun 27 '12 at 20:24
  • $\begingroup$ The case $N=4, m=6$ ought to be within reach; there are $24!/(4!\cdot(6!)^4)\approx 96 \text{billion}$ possible assignments of numbers to dice, with each assignment requiring the $6^4=1296$ different outcomes to be checked, and the projection condition (that any subset of dice also be fair) provides an early-out that should allow a large number of assignments to be automatically culled (e.g., if we find that every face of die $B$ is greater than each face of die $A$, we don't need to distribute the remaining numbers among dice $C$ and $D$) $\endgroup$ – Steven Stadnicki Jun 27 '12 at 20:38
  • $\begingroup$ 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. $\endgroup$ – Steven Stadnicki Jun 27 '12 at 20:42
4
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks! You're the de facto expert on the subject, so I appreciate your weighing in. $\endgroup$ – mjqxxxx Jul 5 '12 at 23:16
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I think the idea is to speak about abstract dice - that is, to have $N$ (multi)sets of $m$ elements, rather than specifically physically-realizeable dice. And I'm not sure your last statement follows; you can certainly assign permutations of players to all of the dice results, but that doesn't mean that you can do it in a way that respects the natural order of the numbers on the dice (which is the point of the idea). $\endgroup$ – Steven Stadnicki Jun 27 '12 at 20:27
  • $\begingroup$ @StevenStadnicki: You are right. I had missed respecting the natural order. Even more it looks very hard for $N \ge 7$ $\endgroup$ – Ross Millikan Jun 27 '12 at 20:38
  • $\begingroup$ 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. $\endgroup$ – Lorenzo Gatti Apr 17 '14 at 7:37
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – mjqxxxx Jan 3 '13 at 21:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.