2
$\begingroup$

There are many dice problems on here so there could be duplicate. If there is I apologize. Here is the question.

The game is given as follows: you are given 5 dice, and the goal of the game is to get all the dice to be showing the same value. On your first roll you roll all the dice, next you can re-roll which ever dice you choose, and you keep doing this until all the dice show the same value. So an example play of the game could go as follows

Roll 1: The dice show 1,1,2,3,4

Roll 2: You leave the two 1's and re-roll the 2,3, and 4 and now the 5 dice show 1,1,1,2,6

Roll 3: Re-roll the 2 and 6 and perhaps we get 1,1,1,1,1 and the game ends because we have all the dice showing the same value.

Here is the question:

Question 1: What is the optimal strategy for minimizing the number of rolls? i.e. if all the dice show different values is it better to re-roll all the dice or choose four to re-roll hoping the the value of the fifth die.

Question 2: Under the optimal strategy, what is the expected number of rolls to end the game?

$\endgroup$
5
  • $\begingroup$ For question 1, if you get five different numbers on the first roll, it doesn't matter whether you keep one or reroll them all. You can think of the kept one as the first one to fall in the reroll. As it doesn't matter what its number is, you may as well keep one. $\endgroup$ Mar 3, 2015 at 23:51
  • $\begingroup$ If you have already kept $11$, and on the next roll get a $444$, is it legal to now keep the $4$'s and reroll the $1$'s? $\endgroup$ Mar 4, 2015 at 0:45
  • $\begingroup$ Mike Earnest. Yes that is an eligible play. You can chose which dice to re-roll every time. $\endgroup$
    – user152558
    Mar 4, 2015 at 1:04
  • 1
    $\begingroup$ The following strategy comes to mind: while( not all dice have same value) find the most occurring value; roll all the dice that have a different value: I wrote a simple c++ program to test this strategy. 1 million games give me the average of 11 moves (counting the first move) which should be your expectation.(NOTE: this may be far off because it relies on random number generation) ideone.com/v8qSIB $\endgroup$ Feb 18, 2016 at 21:56
  • $\begingroup$ @ahmed Elyamani your program is working, since the answer is about $11.31$. +1 because your answer prompted me to check my work and catch an error. $\endgroup$ Jul 31, 2017 at 0:47

2 Answers 2

1
$\begingroup$

First, observe that if no number appears on multiple dice, you could re-roll all or all-but-one with equal effectiveness, so we will simplify by assuming that you will re-roll all.

Let $N(k)$ be the expected number of rolls to bring $k$ dice all onto a specified number. Thus for example $N(1) = 6$.

Now look at $N(2)$. On the next roll (of two dice), you will get no "successes" $\frac{25}{36}$ of the time, one success $\frac{10}{36}$ and two successes $\frac1{36}$ of the time. So $$ N(2) = 1 + \frac{25}{36}N(2)+ \frac{10}{36} N(1) = \frac{16}{6}+ \frac{25}{36}N(2)\\ N(2) = \frac{36}{11}\frac{16}{6}=\frac{96}{11} $$ On the first roll, you will get five identical numbers $\frac{1}{1296}$ of the time; four identical numbers $\frac{25}{1296}$ of the time, three identical numbers $\frac{100}{1296}$ of the time, and all five different $\frac{120}{1296}$ of the time. That last number is calculated by noting that there are six possible values for the missing numbers, and $120$ possible orderings of the five numbers; and the denominator is $6^5$. That means there are two identical numbers (but not three or more) $\frac{1050}{1296}$ of the time.

Unfortunately, the expected number of rolls from a position like $1,1,2,3,4$ is not simply $N(3)$ because the next roll (replacing the $2,3,4$) might be something like $2,2,2$ and that is progress despite not getting any more ones.

The expected number of rolls $E$ in that case is given by $$ E = 1 + \frac{15}{216}N(1)+ \frac{75}{216}N(2)+\frac{5}{216}N(2)+ \frac{120}{216}E $$ where the $\frac{5}{216}$ represents the cases of getting a triplet of some other number. Thus $$ E = \frac{216}{96}\left(1+ \frac{90}{216} + \frac{80}{216} \frac{96}{11} \right) =\frac94+\frac{90}{96}+\frac{80}{11} = \frac{1841}{176} $$ And finally, the expected number $A$ of rolls overall is $$ A = \frac{1296}{1176} \left(1+6\cdot\frac{25}{1296} +\frac{96}{11}\cdot \frac{100}{1296} + \frac{1841}{176} \cdot \frac{1050}{1296}\right) \\ = \frac{1}{1176} \left( 1296+150+\frac{9600}{11}+ \frac{1841\cdot 1050}{176}\right) $$ This works out to just under $11.3112$ rolls.

$\endgroup$
0
$\begingroup$

I believe this could be done rather nicely with Markov Chains. Imagine the 5 states of the game (1,2,3,4,5,E) which correspond to the number of dice that are the same, and E is after the game. Then you can figure out the transition matrix, which is the probability that you go from one state to any of the others:

$P=\left( \begin{array}{cccccc} p(1\rightarrow1)&p(1\rightarrow2)&p(1\rightarrow3)&p(1\rightarrow4)&p(1\rightarrow5)&0\\ 0&p(2\rightarrow2)&p(2\rightarrow3)&p(2\rightarrow4)&p(2\rightarrow5)&0\\ 0&0&p(3\rightarrow3)&p(3\rightarrow4)&p(3\rightarrow5)&0\\ 0&0&0&p(4\rightarrow4)&p(4\rightarrow5)&0\\ 0&0&0&0&0&1\\ 0&0&0&0&0&1\\ \end{array} \right)$

where $p(i\rightarrow j)$ is the probability that you'll start a turn with $i$ dice the same and end it with $j$ the same (not necessarily the same number, so you'd need to be a little careful).

Now you start in state 1, so you can figure out what state you will be in after $n$ turns as:

$\left( \begin{array}{cccccc} 1&0&0&0&0&0 \end{array}\right)\cdot P^n$

This will be an array of 6 numbers, corresponding to the probability that you'll be in each of the 6 states after $n$ turns.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .