People sitting in a circle chewing gum

Question

Ten people are sitting in a circle of ten chairs, chewing gum. Each person spits out his or her gum and places it either under his or her own chair or under an immediately adjacent chair. How many ways can this happen such that every chair ends up with exactly one piece of gum under it?

I tried creating a chart of small values, obtaining for n people, when n = {1, 2, 3, 4, 5}, $f_n$ = {1, 2, 6, 9, 13}

At first I thought tribonacci, as soon as I saw $f_4$ but that notion vanished as I calculated $f_5$

Can someone provide a clear answer and or solution for $f_{10}$? Thanks.

Answer 1

• For $n$ people in a row, not a circle, the number is $Fib(n+1)$. For example for four people there are five possibilities.

• For $n$ people ($n \gt 2$) in a circle:

  • one possibility is that they all shift left; another is that they all shift right
  • the person in seat 1 may use their own chair leaving a row of $n-1$ people
  • the person in seat 1 may use the chair on the right and the person on the right may use seat 1, leaving a row of $n-2$ people
  • the person in seat 1 may use the chair on the left and the person on the left may use seat 1, leaving a row of $n-2$ people

So for $n \gt 2$ the total is $$2+Fib(n)+2Fib(n-1)$$ as you can see in your calculations with $6=2+2+2\times 1$, $9=2+3+2\times 2$, and $13=2+5+2\times 3$.

You can then show $$f_{n+2}=f_{n+1}+f_{n}-2$$ as in $13=9+6-2$.

Answer 2

We can systematically decompose the problem top-down. Let $f(n)$ be the direction in which the $n$-th person (with indices wrapping round the ring) does his disgusting thing, $-1,0,1$ for left, centre and right respectively. Note that the number of ways is equivalent to the number of possible $f$ that satisfies the corresponding conditions, as long as $n \ge 3$. The obvious way is to take out one person. If $f(0) = 0$, then we need to know the number of ways for $(n-1)$ people such that $f(0) \ne 1$ and $f(1) \ne -1$. If $f(0) = 1$, then either $f(1) = -1$ or $f(-1) = 1$. In the first case we need to know the number of ways for $(n-2)$ people such that $f(0) \ne 1$ and $f(1) \ne -1$. In the second case we need to know the number of ways for $(n-1)$ people such that $f(0) = 1$ and $f(1) \ne -1$. I will leave you to verify the bijection in each of these reductions. These reductions tell us to define the following: $\def\nn{\mathbb{N}}$

Let $a(n) = \#(\text{ways for $n$ people such that $f(0) \ne 1$ and $f(1) \ne -1$})$.

Let $b(n) = \#(\text{ways for $n$ people such that $f(0) = 1$ and $f(1) \ne -1$})$.

Then $a(n+2) = a(n+1) + a(n)$ for any $n \in \nn^+$. [Either $f(1) = 0$ or $(f(1),f(2)) = (1,-1)$.]

Also $b(n+1) = b(n)$ for any $n \in \nn^+$. [$f(-1) = 1$.]

You can check that $a(1) = 1$ and $a(2) = 2$, and hence $a(n) = F_{n+1}$ for any $n \in \nn^+$ where $F_n$ is the $n$-th Fibonacci number. You can also check that $b(1) = 1$, and hence $b(n) = 1$ for any $n \in \nn^+$.

Therefore the total number of ways for $n$ people is

  $a(n-1) + 2 a(n-2) + 2 b(n)$

  $\ = F_n + 2 F_{n-1} + 2$

  $\ = F_{n+1} + F_{n-1} + 2$.

Notes

This method gives exactly the same answer as Henry's method, but is more general and can be applied to other more complicated problems without requiring any insight.

Answer 3

There are two 'kinds' of ways for this happening (for $n>2$):
1) All of them are doing the same thing: under his own chair ($1$), to the right ($1$) or to the left ($1$). So there are $3$ ways in this kind.
2) There are some 'pairs' of people and in each pair they place their gum under each other's chair. These sum up as $\displaystyle\frac{n}{1!}+\frac{n(n-3)}{2!}+...$ (here I count the number of ways of $1$ pairs, $2$ pairs, $...) $

Verification of the formula for $n=3,4,5$:
$n=3$: $\displaystyle 3+\frac{3}{1!}=3+3=6$

$n=4$: $\displaystyle 3+\frac{4}{1!}+\frac{4\times 1}{2!}=3+4+2=9$

$n=5$: $\displaystyle 3+\frac{5}{1!}+\frac{5\times 2}{2!}=3+5+5=13$