6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ the final formula is off by one, it's $f_{k+1}$ $\endgroup$ – mercio Feb 20 '17 at 14:47
  • $\begingroup$ shouldn't it be $f_k=(2^k - 2*(-1)^k)/3^k$ $\endgroup$ – TheNotoriousSc Feb 20 '17 at 15:09
  • $\begingroup$ mercio, TheNotoriousSc, thanks, fixed. Sign near $(-1)^k$ is correct, you can check for small $k$. $\endgroup$ – Smylic Feb 20 '17 at 15:35
  • $\begingroup$ The shorter way to get the same answer is appealing to chromatic polynomial of graph $C_n$ that equals to $(x - 1)^n + (-1)^n (x - 1)$ and is the number of proper coloring vertices of $C_n$ in to $x$ colors. So we have $\left.(x - 1)^n + (-1)^n (x - 1)\right|_{x = 3} = 2^n + 2(-1)^n$ is the number of desired orderings of plates and $3^n$ is the total number of orderings of plates, then the answer is $\frac{2^n + 2(-1)^n}{3^n}$. $\endgroup$ – Smylic Feb 20 '17 at 17:14
  • $\begingroup$ Does this take into account that in a circle its the same to order let's say plate1,plate2, plate3 and plate3,plate2,plate1? $\endgroup$ – TheNotoriousSc Mar 2 '17 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.