当前位置: 首页 > >

疯子坐飞机问题

发布时间:

题意:

100人坐飞机,每个人按照编号入座,但第一个人在座位中随便选一个坐下,第100人正确坐到自己坐位的概率是??


他们分别拿到了从1号到100号的座位,这些乘客会按号码顺序登机并应当对号入座


如果他们发现对应号座位被别人坐了,就会在剩下空的座位随便挑一个坐.


现在假设1号乘客疯了(其他人没疯),他会在100个座位中随便选一个座位坐下,问:第100人正确坐到自己坐位的概率是多少?(也可推广到n名乘客n个座位的情况)


思路:

(1) 手动枚举,可以枚举所有的情况,把符合题意的挑选出,多枚举几组样例发现概率恒为1


(2) 递归??


? ? ? 设 P(n) 为第n个人坐在正确位置上的概率


? ? ? 乘客从1-n 编号为 A B C D E .......


? ? ? n = 1 时,P(1) = 1


? ? ? n = 2 时,P(2) = 1/2? ?


? ? ? ? ? ? ? ? ? ? ? 如果A坐在第一个座位上,则B坐在自己座位上的概率为 1*1/2? (两个座位,选择座位的概率同为 1/2)


? ? ? ? ? ? ? ? ? ? ? 如果A坐在最后一个座位上,则B坐在自己座位上的概率为 0


? ? ? ? ? ? ? ? ? ? ? 则 P(2) = 1*1/2 + 0? = 1/2


? ? ? n = 3 时:


? ? ? ? ? ? ? ? ? ? ? 如果A坐在第一个座位上,则C坐在自己座位上的概率为 1/3?(三个座位,选择座位的概率同为 1/3)


? ? ? ? ? ? ? ? ? ? ? 如果A坐在最后一个座位上,则C坐在自己座位上的概率为 0


? ? ? ? ? ? ? ? ? ? ? 如果A坐在第二个座位上,则B可以再第一个和第三个座位中选择一个,这里可以转化一下


? ? ? ? ? ? ? ? ? ? ? B成为了一个新的“疯子”,同上述问题一样,转化成了 B C 之间(两个人)坐在正确位置上的概率


? ? ? ? ? ? ? ? ? ? ? 即概率为? P(2) * 1/3? (这里的 1/3可以看成A在三个位置中选择第二个位置的概率)


? ? ? ? ? ? ? ? ? ? ? P(3) = 1/3 + P(2) * 1/3 = 1/2


? ??


? ? ? ?n = 4 时:


? ? ? ? ? ? ? ? ? ? ? 如果A坐在第一个座位上,则D坐在自己座位上的概率为 1/4?(四个座位,选择座位的概率同为 1/4)


? ? ? ? ? ? ? ? ? ? ? 如果A坐在最后一个座位上,则C坐在自己座位上的概率为 0


? ? ? ? ? ? ? ? ? ? ? 如果A坐在第二个座位上,则B可以在除第二个座位之外中选择一个,这里可以转化一下


? ? ? ? ? ? ? ? ? ? ? B成为了一个新的“疯子”,同上述问题一样,转化成了 B C D 之间(三个人)坐在正确位置上的概率


? ? ? ? ? ? ? ? ? ? ? 即概率为? P(3) * 1/4??


? ? ? ? ? ? ? ? ? ? ? 如果A坐在了第三个座位上,则B可以坐在正确位置上,C将会成为新的疯子,可以转化成在 C D之间求坐在正确位? ? ? ? ? ? ? ? ? ? ? ? ? 置上的概率 即为 P(2) * 1/4


? ? ? ? ? ? ? ? ? ? ? P(4) = 1/4?+ P(3) * 1/4 + P(2) * 1/4 + 0 = 1/2


? ? ?根据归纳法得: P(n) = 1/2


? ? ?可得 P(n+1) = 1/(n+1) + P(n-1) * 1/(n+1) + ....... + P(1) * 1/(n+1)??+ 0 = 1/(n+1) + (n-1/2)*1/(n+1) + 0 = 1/2??


?


可证:?


当 n = 1 时, P = 1


当 n > 1 时, P = 1/2


原文转载



?另一种解释:


我们看看疯子问题是如何转化的:


1.疯子坐对了


问题结束,所有人都可以坐对位置。


2.疯子坐错了,但并没有占据最后一个人的位置


假设疯子坐在了 k 号位置(1,那么从 2到 k-1 号都可以坐对位置,这个时候 k 号乘客进来了。他看到自己的位置被占了,于是重新选择一个位置就座。


注意!


也就是说,在这种情况下,除了 n 变小了,这个问题依然是一个疯子问题!只是 n 变成了 n-k+1 ,而这个第 k 号乘客就是新的「疯子」;而对于每一个疯子,他坐对的位置都是第一个疯子的那个位置。


3.疯子坐错了,而且坐在了最后一个人的位置上


问题结束,最后一个人不能坐在自己的位置上。


所以,第二个选项是无效的,它只是把问题中的n变小了,实质上等于没有做任何选择;且这个过程要么结束,要么会变成 n=2 的情况,这个情况下没有选项 2。


而只有 1 和 3 两个等概率的选项决定了最终结果,它们的概率分别为二分之一。


因此答案是二分之一。



?



其实这个问题还可以更简单。注意到在中间,如果任何一个随机选座位的人坐到了第一个疯子的位置,那么后边的所有人??当然包括最后一个人??就可以坐对。


因此最后一个人的位置只有两种可能:第一个疯子的,他自己的。


这两个位置又没有什么区别,也就是说在各种情况下都是对称的,所以它们的概率相等。


如果还是有问题,下边这个模型你一定能明白。


考虑一枚硬币,正面向上的概率为 1/n ,反面也是,立起来的概率为 (n-2)/n 。我们规定硬币立起来重新抛,但重新抛时,n会至少减小1。求结果为反面的概率。


这样很显然结果为 1/2 。而「正面向上」对应的是下一个疯子坐最后一个人的座位(选项 I);「反面向上」对应下一个疯子坐对的情况(选项 III );「立起来」则对应坐在中间的情况(选项 II)。


作者:王希?
链接:https://www.zhihu.com/question/35950050/answer/65272204?
来源:知乎?



?



友情链接: