首页 > 代码库 > 马后炮一篇 关于Futurama S06E10中的数学问题

马后炮一篇 关于Futurama S06E10中的数学问题

      时间要追溯到2013年9月,我看到过这样一个有趣的问题,来源于matrix67的一篇博文。

那么把题目摘录一下:


“ 经典 Geek 动画 Futurama 上周播出了第 6 季的第 10 集 The Prisoner of Benda 。在这一集中,教授 Farnsworth 发明了一种“心灵对换机”,它可以把两个人的思想互相对换,使得 A 的大脑跑进 B 的身体里,而 B 的大脑则跑到 A 的身体里。 Farnsworth 和 Amy 都想得到对方的身体,便成为了这台机器的第一对实验者。等到他们爽够了想换回来后, Farnsworth 却发现了一个严重的问题:已经互换过大脑的两个身体不能再次进行大脑对换操作。但这并不表示两个人完全没有希望回到自己的身体里—— Farnsworth 突然想到,或许可以用第三者作为一个临时的大脑储存空间,从而实现间接对换。正巧机器人 Bender 进了实验室,于是(身为 Amy 的) Farnsworth 和 Bender 又坐上了机器,这下 Farnsworth 的大脑便跑到 Bender 身体里了,而 Bender 的大脑则进了 Amy 的身体里。此时 Farnsworth 才意识到,引入一个第三者是不够的——再让(身为 Bender 的) Farnsworth 和(身为 Farnsworth 的) Amy 互换大脑,可以让 Farnsworth 恢复原状,但同时 Amy 的大脑会跑到 Bender 的身体里去;这样 Bender 和 Amy 的身体正好颠倒了,而他们却已不能再次使用机器。换句话说,要想恢复两个换位了的大脑,需要引入不止一个新的人。


但现在,问题已经变得更加复杂了——这下已经产生了三个大脑位置错乱的人。大家很容易联想到一个更一般的问题:给定 n 个人以及他们之前使用“心灵对换机”的记录,至少得引入多少个新的人,才能让所有人的大脑都“物归原主”呢?”


条件需要注意的是:n个人两两之间可能都已经换过了,所以后续的交换只能在新人和旧人,新人和新人之间互换。


在原先的文章里,最后给出的解答是这样的:
无论此前n个人的交换有多混乱,最后只需要引入两个人,可以让大家复原。

躯体:1  2  3  4  5  6  …  k-1  k
大脑:2  3  4  5  6  7  …   k   1

首先解答这样一种特殊的情况
2  3  4  5  6  …  k   1  的情况下,可以通过一种构造性的置换方法    
2  3  4  5  6  …  k   1  x  y  
x  3  4  5  6  …  k   1  2  y
x  y  4  5  6  …  k   1  2  3
x  y  3  5  6  …  k   1  2  4
x  y  3  4  6  …  k   1  2  5
x  y  3  4  5  …  k   1  2  6
… … …
x  y  3  4  5  … k-1  1  2  k
x  y  3  4  5  … k-1  k  2  1
x  2  3  4  5  … k-1  k  y  1
1  2  3  4  5  … k-1  k  y  x
1  2  3  4  5  … k-1  k  x y

但是如何面对一般的情形呢?

原文是这样解释的:

“注意到一个 1 到 n 的排列总能分解成若干个循环的乘积,对每个循环分别进行上述操作 ” 

我觉得这句话并没有把这个解答解释得比较充分,让人不太明白,这是这篇文章比较遗憾的地方。


下面说一下我的思考吧


首先,引入这样一个问题。

一个排列,每个数字i都不在第i个位置上,需要多少次交换,才能变换到1,2,3, ..., n-1, n


例如排列 2  4  1  3,最少需要3次交换。排列 2  1  4  3则只需要2次交换。


因为前者{1,2,3,4}构成了一个全乱环,后者{1,2}   {3, 4}构成了2个全乱环(额...全乱环,姑且这么描述吧,暂时没找到正规俗语-_-||)。


排列 1 3 4 2不是我们考虑的情形,因为1在第1个位置。


在一个大小为n的完全乱序环中,最少需要n-1次交换,才能还原。


我们暂时考虑这样的排列:每个数字i都不在排列的第i个位置上,并且需要通过n-1次交换才能还原到1 2 3 4  ... n-1 n


如果只引入一个人x,策略是依次把1,2,3,4心灵换到身体上(红色表示旧人和新人已经做过交换)

2  4  1  3  x

2  4 x  3  1

1  4  x  3  2

1  2  x  3  4

1  2  x  4 3

好,到这里比较尴尬了,因为第一次5号身体和3号已经换过了所以不能再换了


怎么办?


那么只好引入第2个救星了y。他的作用是先和装有1号心灵的身体互换,避免x最后无法交换的困境

2  4  1  3   x  y

2  4  y  3   x  1

x 4  y  3   2  1

x  2  y  3   4  1

x  2  y  4   3  1    

只有x一个人时的困境不再了,3可以和y交换了      

x  2  3 4  y  1

1  2  3  4  y  x

1  2  3  4  x  y

总之,解决的办法就是:

1)y先和1号心灵交换,

2)然后由x的身体把2,3,4,... n按照心灵的顺序各归其位,

3)再由y的身体把1号归位,

4)最后x y互换。


于是,各归其位,世界和平了。 :D

 

等等,我们刚才说了排列中只有一个全乱环的情况,如果有多个全乱环呢?

其实很简单,对每一个全乱环都用上述的方法单独处理就行了。