[转]Futurama中的数学问题 —— 要引入几个新躯体才够？

yylxxch

这个貌似可以建模成线性代数中的序列，然后将打乱的重新排列，根据需要调换的最少次数决定需要添加多少个额外开销。
具体的一时说不清了==

yangti1674

这道题貌似很难啊，需要复杂的计算吗？
悲了个剧，看不懂楼上说的是什么。

晚安

那就拿两个人错位为例…既然知道是常数…
引进一个人之后  错乱的两个人中有一个会回归，这种情况会不断循环下去，也就是说灵魂错乱的最终只会是两个；为了解决这两个，引入新的两个人，就可以全体归位了。

晚安

证明无能 两个 三个 四个的置换俺都玩了一遍

晚安

三个的完全置换（就是所有躯壳之间已经不能再换了）会出现其中有一个灵魂归位的情况，所以N=3其实和N=2是一样的。。

N=4的情况则是以下：

A-a  B-b  C-c  D-d  全部置换一遍，按照A-B,A-C,A-D,B-C,B-D,C-D的顺序最后得到
A-d  B-c  C-b  D-a  这样ABCD之间全部没有置换的机会了 这时引入两个新的躯壳和灵魂

A-d  B-c  C-b  D-a  
E-e  F-f               
置换E和A
A-e  B-c  C-b  D-a  
E-d  F-f
置换E和D
A-e  B-c  C-b  D-d  
E-a  F-f
置换E和F
A-e  B-c  C-b  D-d  
E-f  F-a
置换F和A
A-a  B-c  C-b  D-d  
E-f  F-e
置换F和B
A-a  B-e  C-b  D-d  
E-f  F-c
置换E和C
A-a B-e  C-f  D-d  
E-b  F-c
最后置换E和B、F和C
A-a  B-b  C-c  D-d  
E-e  F-f

应该没错吧

N=5的情况是什么样的呢？
N=5的完全置换情况下，C的灵魂是回归的，也就是说又称为了N=4的情况
N=7的情况也和N=6的情况相同。。。也就是说2n+1和2n的情况相同（n=1开始）

如果是要证明那就是证明2n也就是偶数情况下是什么样的了。。。归纳法 俺不会 扭头

yylxxch

发现一开始把问题复杂化了，原来所谓的两者换完就不能再交换是这么个意思==
那么提供一种方法：假设身体为ABCDE，对应灵魂不妨设为bcdea，且五人间已经不可互换。
引入X，先与E交换得到灵魂a，记为X（a），然后与A交换得到灵魂b，记为X（b），以此类推：当现状态为X（n）时，与N交换。则必然可以一直交换到最后一个，此例为与D交换得到X（e）。X与E交换过，故再引入Y，令X与Y交换得到Y（e），Y与E交换即可。

yylxxch

b.p.bravo 发表于 2010-11-16 17:47
题设是“给定 n 个人以及他们之前使用“心灵对换机”的记录”，没有说大脑混乱是链表升（降）序的。如果 ...

这个无所谓啊，随便找一个开始对换，得到A的灵魂下一轮就和A的身体对换，一直持续下去，必然可以只剩最后一个，再加入第二个机器即可，如上例：
X与A换，得到X（b）、A（x）
X与B换，得到X（d）、B（b）
X与D换，得到X（e）、D（d）
X与E换，得到X（c）、E（e）
Y与C换，得到Y（a）、C（Y）
X与C换，得到X（y）、C（c）
Y与A换，得到Y（x）、A（a）
最后XY呼唤全部完成~

晚安

嗯 同意眼泪君的 我那种想的复杂了= =||||