Construct a fair game with a $N$ sided die

Question

You have a $N$ sided die. And $X$ players. You have to devise a game, such that only one player wins and every player is equally likely to win. Also, the game should be finite (there shouldn't be a single infinite run in the sample space)

Is it possible to construct such a game? (However complicated, doesn't matter) If yes, how?

At the first glance, it seems like it isn't possible, since (For $N=6$) we can only have sample space of the sizes of powers of $2,3,6$. But maybe there exists a complicated game where the sizes are different?

Answer 1

If the game is always finite, let $K$ be the maximum length of the game. We have $N^K$ possible outcomes for $K$ rolls, so the game must assign each player the same number of these outcomes, i.e. $X$ must divide $N^K$.

Now how do we translate the existence of such $K$ to a condition on $N$ and $X$? If $X=p_1^{k_1}p_2^{k_2}\ldots p_l^{k_l}$ (all $k_i>0$), then such $K$ exist if and only if $p_1p_2\ldots p_l$ divides $N$ ($N$ must divide all prime factors of $X$, because otherwise $N^K$ can never be a multiple of $X$). This is sufficient because if we set $K=\text{lcm}(k_1,\ldots,k_l)$, then $X$ divides $N^K$.

We conclude: If $X=p_1^{k_1}p_2^{k_2}\ldots p_l^{k_l}$ (the prime factorisation of $X$), then a fair finite game exists if and only if $p_1p_2\ldots p_l$ divides $N$.

EDIT:

As an example, let us construct a game when $X=20$ and $N=10$: Note that $X=2^2\cdot 5$, so the condition '$p_1p_2\ldots p_l$ divides $N$' becomes $2\cdot 5=10$ divides $N$, which holds for $N=10$. I claim that we can make the game always have 2 rolls. Also, instead of $\{1,\ldots, 10\}$, I will label the outcome of the dice as $\{0,1,\ldots, 9\}$. 2 rolls now look like (5,1), (0,9), (8,7) and so on. Notice that these look like 2 digit numbers, so you see rolling a (0,9) as the number 9 for example. Given that we have 20 players, we can simply divide the 100 possible outcomes (0 to 99) among the players, so each player gets 5 outcomes as their win condition.

Player 1 wins if the 'outcome' is less than 5, i.e. the rolls were (0,0),(0,1),(0,2),(0,3) and (0,4). Player 2 wins if the outcome is between 5 and 10: (0,5),(0,6),(0,7),(0,8) and (0,9). And so on

Answer 2

There exists a fair finite game if $X = N^k, k \in \mathbb{Z}^+$ ending in precisely $k$ rolls of the die (simply enumerate the $X$ players in base $N$) or if $N = kX, k \in \mathbb{Z}^+$ ending in a single roll of the die (enumerate die sides modulo $X$). Otherwise, David Stork's comment applies, though it's not necessarily the case that any particular side of the die will not determine the game (non-terminal conditions can be arbitrarily complicated).

In the interest of answering your question properly, I'll give an example where no such game may be constructed: $X > 1, N = 1$. Any game is deterministic so that only one player can win.

In order for the game to end, there must in general be a terminal condition. This can be in the form of a limit on how many rolls of the die are to be made or in the form of some terminating pattern occurring in the string of rolls. If there is no upper bound on the number of rolls to be made, then there is some pattern which does not terminate the game in any particular number of moves. It follows that the results of the die rolls could avoid any terminal pattern forever; the game is therefore not finite.

---

Anton's supposition that, given an upper limit of $k$ rolls in a game, there are $N^k$ possible outcomes is incorrect. There are at most $N^k$ possible outcomes; there could be early-termination criteria introduced.

Update: @AntonV. has addressed this by noting you can always pad the end of the game with throwaway rolls. This is true; obviously fairness is preserved under these situations (as the odds of each player's win is unaffected). So their answer works.

Answer 3

Let us express the number of players under the binomial coefficient form $X=\binom{N}{n}$ which clearly is always possible.

For example, let us assume there are (as many as) $35$ players. Let us take the form:

$$X=\binom{N}{n}=\binom{7}{3}=35$$

These $35$ players can be placed in bijective correspondence with the subsets with 3 elements

$$abc, abd, abe, abf, acd, ace, \cdots def $$

selected from the set $\{a,b,c,d,e,f\}.$

Said otherwise, in bijective corresponence with the $7$-digits codes with 3 digits "one":

$$1110000, \ 1101000, \ 1100100, \cdots 0000111.$$

There exists a "sampling" algorithm known as Knuth's algorithm S (The Art of Computer Programming, Vol 2, 3.4.2 p.142), as described here allowing to choose $n$ items from a set of $N$ items, with equal probability.

Here is an example with $n=3, N=7$ as above showing the selection of certain subset with code (1010001) [see legend]. with the choosing probabilities given by the $n \times (N-n)=3 \times 4$ array (recall: $n$ is the number of ones and $N-n$ is the number of zeros):

What is the probability of such a path ?

Fig. 1: Selection of the set of 3 elements with code 1010001 using a shortest path between $A$ and $B$: going upwards = 0 (don'take), going leftward = 1 (take).

The probability of taking such a path is :

$$\frac{\color{blue}{3}}{\color{red}{7}}\times\frac{\color{green}{4}}{\color{red}{6}}\times\frac{\color{blue}{2}}{\color{red}{5}}\times\frac{\color{green}{3}}{\color{red}{4}}\times\frac{\color{green}{2}}{\color{red}{3}}\times\frac{\color{green}{1}}{\color{red}{2}}\times\frac{\color{blue}{1}}{\color{red}{1}}=\frac{\color{blue}{3!}\color{green}{4!}}{\color{red}{7!}}=\frac{1}{\binom{7}{3}}$$

establishing equiprobability because, whatever the ranks of the choices, we must "sweep"

• all values $\color{blue}{3,2,1}$ (horizontal sweep),

• all values $\color{green}{4,3,2,1}$ (vertical sweep), both for the numerators and

• all values $\color{red}{7,6,5,4,3,2,1}$ (oblique sweep) for the denominators ...

This probabilistic graph can be traversed in a dynamical way (i.e., without constructing it beforehand) as shown on the following Matlab program:

 n = 3 ; N = 7 ; C = '' ; % C = code to be constructed
 for p = N:-1:1 ; % please note step -1
    s = '0';
    if rand < q/p ; q = q-1 ; s = '1'; end;
    p = p-1; 
    C = [C,s];
 end;

Important restriction (following a remark by miracle173): The previous program uses a "continuous" random number generator "rand" (uniformly distributed over $[0,1)$). The test "$\operatorname{rand}<q/p$" can be transformed into a rigorous discrete equivalent ; for example, testing if $\operatorname{rand}<3/5$ is equivalent to test whether the result issued from (say) a $15$-sided die is larger than $9$.

In order that such a conversion is possible, a sufficient condition is that the die has $N!$ faces.

Remark: in fact, the die should have $a(N)$ faces where $a(N)$ is defined by this OEIS sequence.