Futurama S06E10中的数学问题

     

    经典 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 个人以及他们之前使用“心灵对换机”的记录,至少得引入多少个新的人,才能让所有人的大脑都“物归原主”呢?


(给大家上传一个无字幕版本)

  

    当然,这一集的结局是圆满的: 9 个大脑位置错乱的人,在两个新躯体的帮助下,用了 13 次对换,完成了还原的工作。编剧在剧中给出了一般情况下问题的答案:不管 n 是多少,不管现状有多混乱,引入两个新的身体总是足够的。在剧中,这个结论的证明过程写在了一个黑板上,编剧毫无顾忌地给了黑板一个特写——上面写的真的就是这个结论的证明(点击这里看大图)!

  

 
    这一群编剧来头可不小,他们竟然个个都拿过数学学位。下面,就让我们一起来看看这群变态编剧的证明思路。这是一个构造性的证明。首先,让我们来考虑一种特殊的情形:

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

    换句话说,这些人的脑子所在的位置正好“转了一圈”。我们引入 x 、 y 两个新的人,然后使用下面的策略(每行第 i 个数表示第 i 具躯体里装的谁的大脑,第一行是初始时的状态):

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

(谢谢大家提醒,已更正)

    容易验证,上面所有的对换操作均发生在原来的人与最后两个人之间,而且所有操作都没有重复。也就是说,不管初始时的混乱状态是怎么得到的,引入 x 和 y 之后,这 k 个大脑总能回到自己的身体里去,而 x 和 y 的位置则与初始时颠倒。注意到一个 1 到 n 的排列总能分解成若干个循环的乘积,对每个循环分别进行上述操作,最后如果需要的话就再把 x 和 y 互换一下,问题就解决了。

24 条评论

回复给 biohu 取消回复

  ×  1  =  7