Expected number of moves desperate help Question:You're trying to get a cat, a fish, a dog, and your lunch across a river, but there's a troll in the way. The troll says, "I'll allow you to cross the river, but only if you play this game with me. I have a die here showing a cat, a fish, a dog, and your lunch. I'll roll that die, and then you must bring that item across the river, no matter which side it's on. Once you do that, I'll roll the die again. If you can get everything to the other side, I'll let you go."
You quickly realize this is a bad idea: If you leave the cat and fish alone on one side, the cat will eat the fish, and if you leave the dog and lunch alone on one side, the dog will eat your lunch. (If the cat, the fish, and something else are alone on one side, nothing will be eaten. Likewise, if the dog, your lunch, and something else are alone on one side, nothing will be eaten.) You tell this to the troll, who says, "Fine. When I absolutely need to, I'll re-roll the die to make sure none of your precious cargo is harmed."
Suppose that you make a move when you bring something from one side of the river to the other. (If the troll re-rolls their die, the original roll is disposed of, and this does not count as a move.) Find the expected number of moves you'll need to make before everything is on the other side of the river.
So, this is what I have so far: I let $e_i$ represent the expected value of the number of moves in order for all $i$ items to be on the other side of the bridge. Therefore our goal is to find $e_4.$ However, I am having trouble forming the linear recurrences and it's really frustrating me. Can anybody help? Thanks!
I also know the problem involves states therefore letting me make the states where 4,3,2 or 1 of the things are on the starting side. However, I am also having trouble connecting the relations.
 A: If $S$ is a  subset of $V:=\{\text{cat},\text{fish},\text{dog},\text{lunch}\}$, let $e_S$ be the expected number of moves until success when starting from a situation where the elements of $S$ are on the destination side and the rest are at the source side. A set $S$ is invalid if it results in danger. The invalid sets are  $\{\text{cat},\text{fish}\}$ and $\{\text{dog},\text{lunch}\}$, all other sets are valid. Note that we do not have to account for where you are because a situation where your presence is needed to prevent the cat from eating the fish on one side will automatically imply that the dog will eat your lunch on the other side, and vice versa.
For every $S$, there are up to four possible sucessors, namely for each $x\in\{\text{cat},\text{fish},\text{dog},\text{lunch}\}$, let $$S\Delta\{x\}=\begin{cases}S\setminus \{x\}&\text{if }x\in S\\S\cup\{x\}&\text{if }x\notin S\end{cases}.$$
Then $e_V=0$ and for all valid $S\ne V$, we know that $e_S$ is $1$ plus the average of all $e_{S\Delta\{x\}}$ where $S\Delta\{x\}$ is valid.
To exemplify,
$$e_\emptyset=1+\frac{e_{\{\text{cat}\}}+e_{\{\text{fish}\}}+e_{\{\text{dog}\}}+e_{\{\text{lunch}\}}}4 $$
$$e_{\{\text{cat}\}}=1+\frac{e_{\emptyset}+e_{\{\text{cat},\text{dog}\}}+e_{\{\text{cat},\text{lunch}\}}}3 $$
$$e_{\{\text{cat},\text{dog}\}}=1+\frac{e_{\{\text{dog}\}}+e_{\{\text{cat},\text{fish},\text{dog}\}}+e_{\{\text{cat}\}}+e_{\{\text{cat},\text{dog},\text{lunch}\}}}4 $$
and so on.
This is a system of 14 linear equations in 14 unknowns, from which you ultimately want to find  $e_\emptyset$.
