3 plate dinner problem Consider n people dining in a circular table. Each of them is ordering one of three plates. What is the probability that no two people sitting next to one another will order the same plate?
I intuitively think that every person except the first one has 2 choices as he cannot order the same as the one preceding him. However i can't figure out what happens with the last person as he can have either 1 or 2 choices depending whether the person before him had chosen the same dinner as the first person.
 A: You are considering problem when people are sitting in a line. This is a good idea, but it is not enough to compute probability that it is possible to make a circle from this line. When is it possible? If and only if the last of $n$ people has chosen plate different with previous one and the first one. So we need to compute two sequences: $f_k$ is a probability that $k$ people sitting in the line has ordered plates different for each pair of neighbors and the last one has ordered different plate with the first one, $g_n$ is a probability that $k$ people sitting in the line has ordered plates different for each pair of neighbors and the last one has ordered the same plate as the first one. Then
$$f_1 = 0,\\
g_1 = 1,\\
f_k = \frac{f_{k - 1} + 2g_{k - 1}}{3} \text{ for } k > 1,\\
g_k = \frac{f_{k - 1}}{3} \text{ for } k > 1.$$
Substituting last into penultimate we get:
$$f_k = \frac{3f_{k - 1} + 2f_{k - 2}}{9} \text{ for } k > 2.$$
EDIT.
So
$$f_k = \frac23\left(\left(\frac23\right)^{k - 1} - \left(-\frac13\right)^{k - 1}\right) = \frac{2^k + 2\cdot (-1)^k}{3^k}$$
is the answer for you problem when $k \ge 2$ people are sitting at the table. For $k = 1$ the answer depends on whether this man is next to himself or not.
