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$

1 Answer 1

Reset to default
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$
6
  • $\begingroup$ the final formula is off by one, it's $f_{k+1}$ $\endgroup$
    – mercio
    Feb 20, 2017 at 14:47
  • $\begingroup$ shouldn't it be $f_k=(2^k - 2*(-1)^k)/3^k$ $\endgroup$
    – TheNotoriousSc
    Feb 20, 2017 at 15:09
  • $\begingroup$ mercio, TheNotoriousSc, thanks, fixed. Sign near $(-1)^k$ is correct, you can check for small $k$. $\endgroup$
    – Smylic
    Feb 20, 2017 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, 2017 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, 2017 at 16:38

You must log in to answer this question.

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