我写了一份解题报告看得懂的可以看看:(我以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,证毕。
总结:证明关键:占座链,共轭划分。带*的是一些比较关键的步骤。 |