Futurama S06E10中的数学问题
icon2 Brain Storm | icon4 2010-08-23 21:13| icon322 Comments | 本文内容遵从CC版权协议 转载请注明出自matrix67.com

     

    经典 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 互换一下，问题就解决了。

Posted in Brain Storm
Tags: , , , ,
Trackback: http://www.matrix67.com/blog/archives/3570/trackback
我猜您可能还喜欢：

22 条回复

  • 楼层: 沙发 | 2010-08-23 21:18 | 信息学爱好者 说：

    好强啊！

    PS:OIBH到底怎么了？最近一直挂了！

  • 楼层: 板凳 | 2010-08-23 22:59 | biohu 说：

    太强大了。。。

  • 楼层: 地毯 | 2010-08-23 23:29 | 严酷的魔王 说：

    突然想看这个剧了。。求资源

  • 楼层: 地板 | 2010-08-24 0:00 | layla 说：

    强大的剧啊……

  • 楼层: 地下室 | 2010-08-24 0:06 | 阿饭 说：

    原来黑板上写的那个就是证明方法！我当时还在豆瓣上开贴问有没有人知道证明过程呢！

  • 楼层: 地基 | 2010-08-24 0:14 | 404 说：

    终于有更新。。。赶忙一看发现连地板也没有了= =

  • 楼层: 地壳 | 2010-08-24 1:43 | Elly66 说：

    数学系的学生又多了条出路：做编剧。

  • 楼层: 地幔 | 2010-08-24 5:13 | polly 说：

    can prove it using mathematical induction haha

  • 楼层: 地核 | 2010-08-24 9:04 | BB 说：

    这集实在太重口了。。。。

  • 楼层: 10楼 | 2010-08-24 10:58 | chenxiaoqino 说：

    代码框倒数第二行的
    1 2 3 4 5 … k-1 k y 1
    似乎错了，有两个1.

  • 楼层: 11楼 | 2010-08-24 21:27 | Магсн 说：

    有点像线性代数系统

  • 楼层: 12楼 | 2010-08-24 21:29 | Магсн 说：

    有点像线性代数

  • 楼层: 12a楼 | 2010-08-24 22:53 | 茶盘 说：

    看的我头都大了，好神奇

  • 楼层: 14楼 | 2010-08-24 23:04 | alreadydone 说：

    #10:第一个1应为x

  • 楼层: 15楼 | 2010-08-27 12:11 | 大河 说：

    头大了

  • 楼层: 16楼 | 2010-08-27 16:31 | 于洋 说：

    有机会要看看这个剧集

  • 楼层: 17楼 | 2010-08-28 22:36 | paramecium 说：

    证明框的倒数第二行的第一个数字应该是x吧。

    p.s.弱弱的问一句，构造性的证明是不是就是那种无法解释怎么想到的证明？

  • 楼层: 18楼 | 2010-09-03 21:04 | shilcare 说：

    对不起，这个视频不存在或已被删除。

    被屏蔽了？

  • 楼层: 19楼 | 2010-09-20 11:40 | Zoom.Quiet 说：

    嗯嗯嗯,是否可以用编程的方式来暴力证明?

  • 楼层: 20楼 | 2010-10-04 9:02 | admin(福州51家教网) 说：

    很偶然进入你的 blog
    Feel good and like the challenge of deep thinking
    Perhaps this is the so-called ‘Fate’, right?
    非常谢谢你！

  • 楼层: 21楼 | 2011-04-13 3:05 | `Alice Scarlett 的绝妙小屋 ., » 2011 Spring Trainning Contest SLPC 说：

    [...] 这个题目就是这个东西。。。练习赛的时候我们给出了一种稍稍不同的构造方法。。。（机子坏掉了要花时间补回来啊。。＝ ＝） ?Download F.cpp1 ... [...]

  • 楼层: 22楼 | 2011-08-12 11:23 | orbea jersey 说：

    喔 这个动画很不错！

您也随便说几句吧：

您可以在 Gravatar 设置您的头像。