九连环的解法秘籍.docx

基本玩法只有两个动作P和Q，而且在状态000000000和000000001只能进行一个动作P，其他状态可以进行两个动作P,Q。打个比喻，就好像一个人沿着一条线走。在线的始点，他只能前进一步。在线的终点，他只能后退一步。在线的中间，他可以向前一步或后退一步。但在具体的一次行进中，为了由某一个位置到另外一个位置，他要么总是向前，要么总是向后，不可一会儿前进一会儿后退，因为那是走回头路，徒劳无益。如果记录他的各步，要么是连续的前进前进再前进，没有后退；要么是连续的后退后退再后退，没有前进。??? 玩九连环当然也是这样，不过，动作P和Q，并不是简单的对应于前进和后退。根据规则4，连续的动作PP，或者QQ，必然是原地不动。所以，如果某个状态下，动作P是前进，那么接下来如果再做动作P就是后退，而动作Q才是前进；反之，如果动作Q是前进，那么接下来的动作中，再做动作Q就是后退而动作P才是前进。记录玩九连环的各步，只能是P和Q相间出现，而不能连续出现P或者连续出现Q。于是，同样是连续的前进前进再前进，没有后退；或者是连续的后退后退再后退，没有前进，但各个动作记录下来却是交错的序列：…PQPQP…。??? 可以用图来表示如下，并称之为“状态图”。状态图是解决很多趣味数学问题的工具。图中小圆圈表示九连环的状态，称为点，两个小圆圈间的线段表示动作，称为边。下面不再区分九连环的状态和图中的点，也不区分九连环的动作和图中的边。点就是状态，边就是动作。两个点（小圆圈）间的边数（线段数）称为这两个点（即两个状态）间的距离。这也确实就是数学中图论的讨论对象，关于图论的进一步请参看迷宫部分。图7??? 状态000000000和终点000000001都只连接1条边，相当于路线的端点，也就是玩九连环的过程的两个端点，为了方便讨论，我们规定始点是000000000，终点000000001，其他状态称作中间状态。由于在状态000000000和000000001只能进行动作P，故不论从始点到终点，还是从终点到始点，这个动作序列总是由P开头也由P结束，即动作序列为PQPQPQ…PQPQP。??? 这样，我们只对九连环做了点初步的分析，就已经初步知道玩九连环是怎么一回事了。比如从九个环都在下边，即从状始，只要按照PQPQP…做下去，最终会成为000000001，且最后一步动作必是P。反之，如果一开始是终点000000001，仅9号环在上边，也只要按照PQPQP…做下去，最终也会把九个环都下下去成为始且最后一步动作也必是P。??? 说是“初步”的会玩，指的是我们还只会机械地连续操作，一旦中断一下，再开始时如果忘记了刚才最后做的是哪个动作，那就惨了，说不定就会会到初始状态去。这原因是我们仅知道了在始点和终点间变化，而从任意一个状态到另外任意一个状态应该怎样操作，还不知道。??? 另外我们还有很多问题没有解决，例如，从始点，按照PQPQP…做下去，最终会成为终点000000001吗？还是永远也到达不了终点？如果能到，要多少步数？九连环有多少不同的状态，从始点，按照PQPQP…做下去，能出现所有的状态吗？解决了这些问题，我们才算是理解了基本玩法。基本玩法的分析??? 下面讨论几个问题。1．九连环有多少状态？??? 这就是从0，1中可重复的取九个元素做排列，其排列数为29=512，即有512个状态。表示为000000000，100000000，010000000，110000000，001000000，……。2．九连环动作的图真的是这样一条路线吗？或者说，其中有没有分叉，或圈？ ??? 问得好，提这个问题要有相当的思考习惯和能力。可以证明这个图确实就是一条路线。（1）从状态000000000开始，连续进行动作PQPQPQ…，出现的九连环的状态不会重复。??? 从状态000000000开始，只能进行动作P，下一步必然到达状态100000000。此时可以进行动作P，也可进行动作Q。但根据规则4，只能进行动作Q，得到再下一个状态。如此进行，得到九连环的许多状态。这些状态是不会重复出现的，下面用反证法证明。??? 把出现的一系列状态记作A0, A1, A2, …,An, …，其中A0是始点000000000。我们依次检查每个新出现的状态，假设第一个出现与它前面的状态有重复的是状态An，而与它重复的状态是Ak(0≤k＜n)，如图。图8??? 也就是说，在A0, A1, A2, …,An中，只有Ak=An，其他再无相同的点。考虑Ak与几个不同的点相连。首先，Ak与An－1相连，又与Ak+1相连。如果k＞0（即Ak不是始点），Ak还与Ak－1相连。因此如果Ak是中间状态，它与三个点Ak－1,Ak,An-1相连，但我们知道，任何一个中间点顶多与两个点相连，矛盾