九连环的数学原理
最近正好看到一道题跟九连环有关，而自己连九连环都不会
所以今天就来写一篇文章讲讲九连环的数学原理吧。
顺便搬了一个 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_1 = 1,~f_2 = 2$ 。
当然递推式还不够美观，我们来求一下它的通项公式。
设 $g_n = f_n+\frac{1}{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}$ ，即
整理得
参考文献：
