Dice Game - Probability Theory 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?
 A: 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.
