九连环的数学原理
最近正好看到一道题跟九连环有关，而自己连九连环都不会
所以今天就来写一篇文章讲讲九连环的数学原理吧。
顺便搬了一个 javascript 写的模拟器，博客内链接 （原链接见参考文献[1]）
不妨记环在杆子上则状态为 \(1\) ，反之为 \(0\) ，并用 \(a_i\) 表示环 \(i\) 的状态。
稍微玩一玩可以发现，九连环有且仅有两种操作方式
- 改变位置最左侧的环的那个状态
- 改变位置为 \(i~(2 \le i \le 9)\) 的环，且 \(i\) 满足 \(a_{i-1} = 1 \,\land\,\forall 1\le j <i-1,~a_j=0\) 。
操作二可能不太形象，但是如果大家手头有九连环的话应该就知道怎么取出来了。
那么怎么解开这个九连环呢？容易发现，上述两个操作均为可逆操作，且不存在其他更多的操作方式。
这里操作的可逆性体现在 \(S_n\cdot A \cdot A = S_n\) ，也就是重复两次同一操作可以变回原状态，这点很显然。
因此只有 \(A,B,A,B\) 的操作和 \(B,A,B,A\) 的操作可以让九连环的状态发生改变。
这实际上就是在问第一步应当做操作一还是操作二，显然传统九连环的初始状态做操作一更有意义。
于是九连环的解法就是简单的 \(A,B,A,B\) 直到被解开，由于可逆性，我们可以反过来再装回去。
当然了，最后一个操作也一定是 \(A\) ，因为结束前的最后一个状态为 \(100000000\) ，不能进行 \(B\) 操作。
如果理解了这个原理，那么给出任意时刻的九连环都可以解开了。然后我们再来推广一下。
设 \(f_n\) 表示 \(n\) 环的操作数，那么有递推式 \[ f_n = f_{n-1}+2f_{n-2}+1 \] 边界 \(f_1 = 1,~f_2 = 2\) 。
当然递推式还不够美观，我们来求一下它的通项公式。
设 \(g_n = f_n+\frac{1}{2}\) ，递推式 \[ g_n = g_{n-1} + 2g_{n-2} \] 边界 \(g_1 = \frac{3}{2},~g_2 = \frac{5}{2}\) 。
特征方程 \(x^2 - x - 2 = 0\) 解得 \(x_1 = -1,~x_2 = 2\) ，则 \(g_n = c_1\cdot(-1)^{n-1} + c_2\cdot2^{n-1}\)
代入 \(g_1,g_2\) ，解得 \(c_1 = \frac{1}{6},~c_2 = \frac{4}{3}\) ，即 \[ f_n = \frac{1}{6}(-1)^{n-1} + \frac{1}{3}\cdot2^{n+1} - \frac{1}{2} \] 整理得 \[ f_n = \frac{1}{6}\times\left[2^{n+2}+(-1)^{n-1}-3\right] \]
参考文献：
