题目

100人坐飞机，第一个乘客在座位中随便选一个坐下，第100人正确坐到自己坐位的概率是？ 他们分别拿到了从1号到100号的座位，这些乘客会按号码顺序登机并应当对号入座，如果他们发现对应号座位被别人坐了，就会在剩下空的座位随便挑一个坐．现在假设1号乘客疯了（其他人没疯），他会在100个座位中随便选一个座位坐下，问：第100人正确坐到自己坐位的概率是多少？（也可推广到n名乘客n个座位的情况）

• 1号第一次选择1号座位，结束。

• 1号选择做100号座位，则对2~99号来说不用考虑，100号只能坐1号座位。

• 1号第一次选择33号座位，则对2~32号来说不用考虑
• 33号选择96号座位，则对34~95号来说不用考虑，还剩下1、97、98、99、100
• 96号选择100号座位，则对97~99号来说不用考虑，100号只能座1号座位
• 就这样整个选择一直持续，都归结为两个状态———有没有坐在1号或者100号座位
• 而这两种选择是等可能的。
 

这题结果是1/2 知乎看见一个很巧妙的思路就是：2-99号如果发现1号疯子占了自己的位置，就只能随机坐到位置x上，这等价于他们让疯子把自己的位置让出来，然后让疯子去坐x，这并不影响后面人的局面，所以到最后2-99都在自己位子上，疯子可能在1也可能在100，所以就是1/2的概率。 还有一个思路是：分成三种情况讨论，第一种疯子坐对了、没事，第二种疯子坐到了第k个位置、那么2-(k-1)的人都坐对，对于第k个人来说、这又变成了一个疯子问题，第三种疯子坐到了第100个位置结束。所以第二个情况实际上无效，因为它变成了n小一些的子问题，那么只要看第一种和第三种的情况，这俩概率一样的，所以最后就是1/2。（这个思路也可以写成递推形式） 按照随机顺序上飞机之后，正常人是会好好坐的，所以只要看疯子是第几个上飞机，疯子最后一个上飞机肯定坐对，这是1*1/n，如果疯子不是最后一个上飞机那么疯子前面的人都是对的，后面其实就相当于疯子第一问第一个上飞机的问题，是(1/2)*(n-1/n)，加起来就是(n+1)/2n 宁夏区域赛的那个题「Take Your Seat」是这样的：第一问和上面一样，第二问是大家会按照一个随机的顺序上飞机。（唉那个题当时还是我推的，结果面试考反倒没答出来，还是思路没那么清楚啊）