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:
- No two faces share a label (so no ties can occur).
- 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?