[盖棺定论]纯数学证明*有关问题，精确为1/2，欢迎讨论，转载请注明ID~
[盖棺定论]纯数学证明*问题，精确为1/2，欢迎讨论，转载请注明ID~~~
前些日子，偶然在版内看到此题目，深感这是道好题目，好到什么程度？略加思索竟不知道该运用什么知识解此题。早上去学校，翻阅组合数学书籍，终于得到灵感，不敢私藏，特与大家分享~~
PS：此题凭心而论，超出了大多数朋友的数学能力范围，我还没有找到更好的方法证明此题目
先把题目抄下：（为方便起见，我以N=4举例说明，此例N=100
100个人排队乘坐有100个座位的飞机，正常情况时每个都都会对号入坐，但是，第一个上飞机的是个*，他随机坐了一个位子，接下来的人上飞机时，如果自己座位被人坐了就会随机找个座位坐下，否则就坐自己坐位。问题：最后一个上飞机的人坐到自己座位的概率是多少？？
解：
假设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，证毕。
总结：证明关键：占座链，共轭划分。带*的是一些比较关键的步骤。
------解决方案--------------------
我有个更简单的证法：
设第n个人（不算*）座位被占用的概率为f(n)，而她的座位被占的情况下，她只有可能去占剩下的N－n＋1个位置（因为前面n-1个已经被占了），所以她占用别人的座位的概率是1/(N－n＋1)。显然f(2)=1/N.
于是可以推断第n个人座位被占的概率为她的座位被各个人占用的概率之和
即：f(n)=f(1)*1/N+f(2)*1/(N-1)+……+f(n-1)*1/(N-n+2)
于是有f(n)-f(n-1)=f(n-1)*1/(N-n+2) 可以得到(N+2-n)*f(n)=(N+2-(n-1))*f(n-1)
不妨设g(n)=(N+2-n)*f(n),于是有g(n)=g(n-1)=……=g(2)=(N+2-2)*f(2)=1
f(n)=1/(N+2-n) 所以f(N)=1/2
------解决方案--------------------
fortress的证明非常好！
另外我用归纳法给点意见：
N为排队坐飞机的人数
已知N=2时，概率rate为1/2；
假设：在N为2 ~ t-1时rate=1/2;则N=t时，rate=1/2;（t-1> =2）
证：t个人坐飞机，*以1/t的概率座到第m(2 <=m <=t)的座位，相当于第m个人变成*，问题成了一个t-m+1个人的原问题，此问题的rate=1/2(由假设)，
所以N=t时，rate=1/t+(1/t)(0.5*(t-2))=0.5;
所以假设成立；
得出任何人排队坐飞机都是相同的结果1/2
前些日子，偶然在版内看到此题目，深感这是道好题目，好到什么程度？略加思索竟不知道该运用什么知识解此题。早上去学校，翻阅组合数学书籍，终于得到灵感，不敢私藏，特与大家分享~~
PS：此题凭心而论，超出了大多数朋友的数学能力范围，我还没有找到更好的方法证明此题目
先把题目抄下：（为方便起见，我以N=4举例说明，此例N=100
100个人排队乘坐有100个座位的飞机，正常情况时每个都都会对号入坐，但是，第一个上飞机的是个*，他随机坐了一个位子，接下来的人上飞机时，如果自己座位被人坐了就会随机找个座位坐下，否则就坐自己坐位。问题：最后一个上飞机的人坐到自己座位的概率是多少？？
解：
假设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，证毕。
总结：证明关键：占座链，共轭划分。带*的是一些比较关键的步骤。
------解决方案--------------------
我有个更简单的证法：
设第n个人（不算*）座位被占用的概率为f(n)，而她的座位被占的情况下，她只有可能去占剩下的N－n＋1个位置（因为前面n-1个已经被占了），所以她占用别人的座位的概率是1/(N－n＋1)。显然f(2)=1/N.
于是可以推断第n个人座位被占的概率为她的座位被各个人占用的概率之和
即：f(n)=f(1)*1/N+f(2)*1/(N-1)+……+f(n-1)*1/(N-n+2)
于是有f(n)-f(n-1)=f(n-1)*1/(N-n+2) 可以得到(N+2-n)*f(n)=(N+2-(n-1))*f(n-1)
不妨设g(n)=(N+2-n)*f(n),于是有g(n)=g(n-1)=……=g(2)=(N+2-2)*f(2)=1
f(n)=1/(N+2-n) 所以f(N)=1/2
------解决方案--------------------
fortress的证明非常好！
另外我用归纳法给点意见：
N为排队坐飞机的人数
已知N=2时，概率rate为1/2；
假设：在N为2 ~ t-1时rate=1/2;则N=t时，rate=1/2;（t-1> =2）
证：t个人坐飞机，*以1/t的概率座到第m(2 <=m <=t)的座位，相当于第m个人变成*，问题成了一个t-m+1个人的原问题，此问题的rate=1/2(由假设)，
所以N=t时，rate=1/t+(1/t)(0.5*(t-2))=0.5;
所以假设成立；
得出任何人排队坐飞机都是相同的结果1/2