Podemos descomponer sistemáticamente el problema de arriba hacia abajo. Deje $f(n)$ ser la dirección en la que el $n$-th persona (con índices de envoltura alrededor del anillo) hace su cosa asquerosa, $-1,0,1$ para la izquierda, centro y derecha, respectivamente. Tenga en cuenta que el número de maneras es equivalente al número de posibles $f$ que satisface las condiciones correspondientes, mientras $n \ge 3$. La manera más obvia es llevar a cabo una sola persona. Si $f(0) = 0$, entonces necesitamos saber el número de formas para $(n-1)$ personas que $f(0) \ne 1$$f(1) \ne -1$. Si $f(0) = 1$, entonces cualquiera de las $f(1) = -1$ o $f(-1) = 1$. En el primer caso necesitamos saber el número de formas para $(n-2)$ personas que $f(0) \ne 1$$f(1) \ne -1$. En el segundo caso, necesitamos saber el número de formas para $(n-1)$ personas que $f(0) = 1$$f(1) \ne -1$. Voy a dejar a usted para verificar la bijection en cada una de estas reducciones. Estas reducciones decirnos que nos defina los siguientes:
$\def\nn{\mathbb{N}}$
Deje $a(n) = \#(\text{ways for $n$ people such that $f(0) \ne 1$ and $f(1) \ne -1$})$.
Deje $b(n) = \#(\text{ways for $n$ people such that $f(0) = 1$ and $f(1) \ne -1$})$.
A continuación, $a(n+2) = a(n+1) + a(n)$ cualquier $n \in \nn^+$. [O $f(1) = 0$ o $(f(1),f(2)) = (1,-1)$.]
También se $b(n+1) = b(n)$ para cualquier $n \in \nn^+$. [$f(-1) = 1$.]
Se puede comprobar que $a(1) = 1$$a(2) = 2$, y, por tanto, $a(n) = F_{n+1}$ cualquier $n \in \nn^+$ donde $F_n$ $n$- ésimo número de Fibonacci. También se puede comprobar que el $b(1) = 1$, y, por tanto, $b(n) = 1$ cualquier $n \in \nn^+$.
Por lo tanto, el número total de maneras para $n$ de la gente es
$a(n-1) + 2 a(n-2) + 2 b(n)$
$\ = F_n + 2 F_{n-1} + 2$
$\ = F_{n+1} + F_{n-1} + 2$.
Notas
Este método nos da exactamente la misma respuesta como Henry's método, pero es más general y puede ser aplicado a otros problemas más complicados sin necesidad de ningún conocimiento.
