Tenzi

Basic Puzzle (\(n\)=3)

Let \(Y\) be the random variable which denotes the number of dice left on the table after the first roll of \(n=3\) dice. Let \(X_1, \dots, X_n\) denote the random variables which represent each of the \(n\) dice.

Now if we want \(Y=1\), we need all 3 dice to be different. If all 3 dice were different, we must make a choice, which dice to leave on the table. If we pick uniformly at random, we pick each dice with probability \(1/3\).

Thus, for \(Y=1\), . Thus, we have 6 choices for the first dice, 5 choices for the second dice and 4 choices for third die. However, there are \(\binom{3}{1}\) choices for each dice to be the first dice.

\[\begin{align*} \text{ }\text{Pr}\left[Y=1\right] &= \frac{6 \times 5 \times 4}{6^3} \times \frac{1}{3}\times \binom{3}{1} &= 20/36 \end{align*}\]

Now for \(Y=2\), we need any 2 dice to be the same. Thus, we have 6 choices for the first dice, which decides the second dice, and then 5 choices for the third. However, we have 3 ways to select 2 dice. There is no randomness for which dices stay on the table (the two that were same).

\[\begin{align*} \text{ }\text{Pr}\left[Y=2\right] &= \frac{6\times5}{6^3}\times 1 \times \binom{3}{2} &= 15/36 \end{align*}\]

For \(Y=3\), we need all 3 dice to be the samne. Thus, we have 6 choices for the first dice, and that determines everything else.

\[\begin{align*} \text{ }\text{Pr}\left[Y=3\right] &= \frac{6}{6^3} \times 1 \times \binom{3}{3} &= 1/36 \end{align*}\]

Thus, we have

\[\mathbb{E}\left[Y\right] = 1\frac{20}{36} + 2\frac{15}{36} + 3\frac{1}{36} = 53/36\]

Extra Credit

We use shorthand \(Z= 1/6^n\). For any given value of \(n, y\) we ask the following questions:

• How many options are there for the dice in the first group? How many for the dice in the second group etc. (note that there can only ever be at most 6 groups and there must be at least 1 group regardless of \(n\).)
• How many dice are combined into a group?
• How many groups are competing to stay on the table?

These questions are best illustrated with an example:

\(n=4\)

• \(Y=1\), need all 4 dice to be different. So to answer the first question, we have 6 options for the first dice, 5 ways for the second, and so on. Now we can select. Each group that is being kept on the table is being combined into a group of size 1. There are \(\binom{4}{1}\) ways of making these groups. Finally, there are 4 groups competing to be selected as the leader. This gives us:

\[\text{ }\text{Pr}\left[Y=1\right]= \frac{1}{Z}\cdot(6*5*4*3) \times \binom{4}{1} \times 1/4\]

• For \(Y=2\) the situation is more complex. We can either have 2 groups of 2 or 1 group of 2 and 2 different dice. For the first case, there are 6 options for the first group, and 5 options for the second group. There 4 choose 2 ways to make 2 groups of 2, and once we’ve formed these groups, each group can be a leader with probability 1/2. For the second case, there are \(6\times5\times4\) ways of picking 2 unique dice and 2 same dice and 4 choose 2 ways of picking 2 dice to be in the same group. This gives us

\[\text{ }\text{Pr}\left[Y=2\right]= \frac{1}{Z}\cdot(6*5) \times \binom{4}{2} \times 1/2 + (6*5*4*\binom{4}{2})\]

• For \(Y=3\) we have 6 options for the group of 3 and 5 options for single different dice. There are 4 choose 3 ways to make a group of 3, and once a group is formed it is the only one that can stay on the table.

\[\text{ }\text{Pr}\left[Y=3\right]= \frac{1}{Z}\cdot(6*5) \times \binom{4}{3}\]

• For \(Y=4\) all dice has to be the same color, so

\[\text{ }\text{Pr}\left[Y=4\right]= \frac{1}{6^{3}}\]

\(n=10\)

I could not come up with a closed form solution for \(n\)=10. The above analysis works but there’s a lot of cases to keep track of. For examples \(Y=3\), we could have the following arrangements, where each cell represents a dice color/number.

[3,3,3,1,0,0] + [3,3,2,2,0,0] + [3,3,2,1,1,0] + [3,3,1,1,1,1] + 
[3, 2, 2, 2, 1, 0] 

I conjecture there is a dynamic programming based solution here, where each case decomposes into multiple smaller cases). However, if we’re just looking for an answer, Monte Carlo simulation works.

Answer empirical 3.44945

import numpy as np
import pandas as pd
from collections import Counter
def many_left(lst):
    return Counter(lst).most_common()[0][1]
        
num_trials = 80000
for num_dice in [3]:
    print("n={}".format(num_dice))
    data = {i+1: 0 for i in range(num_dice)}
    for _ in range(num_trials):                        
        sample = np.random.randint(6, size=num_dice)
        data[many_left(sample)] += 1
    df = pd.Series(data)/num_trials            
    ans = sum([idx*val for idx, val in df.items()])
    print('Answer empirical', ans)
    print('='*80)