趣题:丢失的机票 一个有趣的概率问题

    一架客机上有100个座位,100个人排队依次登机。第一个乘客把机票搞丢了,但他仍被允许登机。由于他不知道他的座位在哪儿,他就随机选了一个座位坐下。以后每一个乘客登机时,如果他的座位是空着的,那么就在他的座位坐下;否则,他就随机选一个仍然空着的座位坐下。请问,最后一个人登机时发现唯一剩下的空位正好就是他的,其概率是多少?

    当最后一个乘客登机时,最后一个空位要么就是他的,要么就是第一个乘客的。由于所有人选择座位时都是随机选择的,这两个位置的“地位”相等,它们所面对的“命运”是相同的,不存在哪个概率大哪个概率小的问题。因此,它们成为最后一个空位的概率是均等的。也就是说,最后一个人发现剩下的空位正好是他的,其概率为50%。

来源:cut-the-knot
不知不觉地,这已经是第400篇日志了

17 条评论

  • Rache

    不知道这是不是第400个沙发

  • deoxyz

    问一下M67对clrs概率那章 最后一个题的看法( c 2.10 )我感觉跟mouty hall问题蛮象的 (c 2.09 就是羊与车问题吧)

    回复:两道题实质上是一样的

  • jjymhkx0820

    …这个用递归考虑到50%的概率到不难,难的是想到:"当最后一个乘客登机时,最后一个空位要么就是他的,要么就是第一个乘客的。"…

    回复:就是啊……

  • why_cut_the_knot

    M67,很严肃地问一下:
          为什么我上不了cut-the-knot ?老是转到
    http://www.cut-the-knot.org/errors/blank.htm

    回复:不会啊,我浏览起来很正常
    你换个浏览器试试

  • water

    由于所有人选择座位时都是随机选择的,这两个位置的“地位”相等,
    这句话怎么理解,我想不通。

  • sss正和

    地下室的疑问有道理,我也觉得这个结论一点也不显然。我给出一个论证:把登机人的座位从第二个人开始依次排成一列,第一个人的座位排在最后。显然,第一个人选中倒数第二个或最后一个位置的概率是相等的。如果第一个人没有选中最后两个,则视为选择未结束;设他选中的是第k个,则后面紧接的k-1人没有选择(都坐自己的位置),选择权转交到第k人手中继续前面未结束的选择;第k人的地位此时与前面的选择者完全相当,余类推。最后两个位置被前面的选择者选中的概率始终相等,选择迟早会结束,因此轮到最后一个人时,倒数第二个位置有50%概率空着,那是他自己的正确位置。

  • chichi

    我觉得这样想能更简单地理解,当最后一个乘客登机时,最后一个空位要么就是他的,要么就是第一个乘客的,这句话肯定是对的。
    那么第一个坐了自己的,最后的人也坐了自己的;第一个坐了最后那个人的位子,那么最后那个人坐了第一个人的位子,这两个概率是一样的。
    其他的情况就是第一人坐了剩下98个位子中一个,对于这98人来说,第一个人的位子和最后一个人的位子完全等价,并且选择是互斥的,各50%的可能选择。
    综上,50%是正解。

  • wendao

    为什么前面座位被占的人不会随机坐到第一个人的位置上?

  • wendao

    啊,对的,一旦有人坐到第一个人位置上后面人都会坐到自己位置上了……

  • colayoung

    我觉得用对应的观点更好理解一点,假设1号人坐在k号位上,则后面的 2 到 k-1 号 人都坐的原位,所以 k只能做到大于等于他自己号码或者一号人的座位上,如果坐到1号位,后面的人都坐原位,循环结束,否则这个继续下去,最终必定会循环到1,而且只会出现一个循环链,所以可以将所有可能性和 2到100 构成的所有子集构成一一对应,而最后一个人能不能坐到原位 就看 该对应的子集是不是包含100 这显然是等可能的,所以概率分别为50%

  • augurlaolao

    我觉得没有讨论的必要性。。。

  • zxy_ee

    感觉貌似可以这么理解:假如剩下的位置不是第一个人和最后一个人的话,那这个位置的主人为什么不坐在自己的位置上呢,而要让它空着?

  • TomLenen

    貌似Puzzle Toad这一个和这个有异曲同工之妙:http://www.cs.cmu.edu/puzzle/puzzle29.html

  • cervelo jersey

    循环结束,否则这个继续下去,最终必定会循环到1,而且只会出现一个循环链,所以可以将所有可能性和 2到100 构成的所有子集构成一一对应

  • yourname

    看来我们课本上的1%错了…

  • ffffffff

    还有一种想法自认为也很亲民
    假设把飞机上所有的100个位置分成3组:第一个乘客的位置,中间98个乘客的位置以及最后一名乘客的位置。
    那么乘客上机之后的选择有三种可能:正好选中自己的位置,选择中间98个乘客中其中一个人的位置或者是选了最后一个乘客的位置。其中,
    1)他正好选中自己位置。则必然有最后一个乘客能坐上自己的位置。几率是1/100。
    2)如果他选了选择中间98个乘客中其中一个人的位置(概率是98/100),有可能导致最后一个乘客刚好能坐上自己的位置,前提是某一个乘客,假设选到最后(把98个座位都坐满了),也就是第99个乘客,发现自己的位置被坐了,并且选了第一个乘客的位置。那概率就应该是 98/100*1/2 (贝叶斯公式)。
    3)如果第一个乘客坐了最后一个乘客的位置,那么乘客坐上自己的座位的几率就是0。所以最后一个乘客能坐上自己位置的概率就是情况1)+情况2)= 1/100 + 98/100*1/2=50/100=1/2.
    结果同楼主答案。

  • 匿名

    这题其实除了题主给的最讨巧的解法以外,最不需要思考的方法是用数学归纳法,从N=1开始分析。

发表评论

  +  55  =  63