我写了一份解题报告看得懂的可以看看：(我以N=4举例说明)
假设p是满足题目要求的一个n全排列，如1234表示第一个人做1号位置,以此类推，傻子编号为1,全部满足题目要求的排列集合为{p};
*1、当第k个人上飞机的时候，他不可能做到编号为2到k-1的座位上。
证明：假设他能坐到第i个坐位上（2<=i<=k-1),则表示，第i个人上飞机的时候，第i个座位是空着的，那么他就该坐到第i个座位上，则第k个人不可能坐到i号上。
推论1：第N个人上飞机的时候，他只能坐在1号或者N
2、用P1,P2等表示第n个人，若Pi占了Pj的座位，则做有向边Pi->Pj.形成有向图G
2-1;G中任意顶点的度：入度和出度为1或度为0
*2-2:G中最多存在一个连通分部（G')，包含2个或2个以上的顶点，且P1属于G'
2-3:由以上两点，可知若G'存在，则构成一单向连通的循环链,若不存在,则补充 定义G'只包含P1.
3、定义p中的一个错排序列s,满足：
（1）第一个元素在序列头，1在序列中结尾
（2）除1外，序列中其他元素单调递增加
（3）p中不存在比s更长的满足定义的序列
举例：p=1234,s=1;
p=2134,s=21
p=3214,s=31
p=2314,s=231
p=2341,s=2341
易见，s的实际意义就是一个排列中，没有坐在自己座位上的的人的一个“循环占坐链”，在排列2314中，s=231，表示第1个人占一2号座位，第2个人占了第三个座位，而第三个人占了1号座位。也就是2中定义的单向循环链G'
4、p和s存在一一对应关系。
p->唯一s,已经在2中证明了,s->p,也很显然，因为N中不在s中的数字，必然要在自己原来的位置上，这个排列当然是唯一的。
5、从s到p，方法在4中已经说明了
举例N=4：
s={3,1},{N}-s={2,4},先将2插入到第二个位置，再将4插入到第四个位置
s={2,3,4,1},{N}-s=空集，所以s本身就是p
*6、推论：假设第k个人占了1号座位，在他之前被占的最大座位号是q,则从第q+1个人开始，依座位号就座。（很强的结论）
7、s和p的个数
由s的产生，可s为2到N的一个全组合并上{1},由二项定理，可知对于N,满足的排列总数为2^(N-1)
*8、 定义s的一个共轭为s'={x|x=1或x不属于N}
s={1}.s'={2,3,4,1}
s={2,1|,s'={3,4,1}
s={3,1},s'={2,4,1}
对{s}做一划分，划分的依据是是否包含4(N),由于s不存在自共轭，立刻可知这两部分所含元素相等，同为2^(N-2)
9、证明：当最后一人上飞机后，他坐在自己的位置上当且仅当排列p的生成s不包含{N}
充分性：若s不包含N,则s中的最大数q<N-1.根据推论6，当N>=k>=q+1,最后一人必然坐在自己的座位上。
必要性：根据s的定义。
10、由结论8和结论9，可知，此题答案为1/2，证毕。
总结：证明关键：占座链，共轭划分。带*的是一些比较关键的步骤。 |
狗仔卡
发表于 2008-4-30 18:40
提升卡
置顶卡
变色卡
发表于 2008-4-30 21:56
发表于 2008-5-4 14:01
