The Lost Boarding Pass

LeetCode 1227

Solution

问题描述

$N$个人依次登机,只有第一个人忘记了自己的座位号,他随便找了个位置坐下,随后的人按以下规则入座:

  • 如果自己的座位没被占,坐自己的位置,
  • 如果自己的位置被占了,随便找个位置坐下.

问题:

  • 原题,最后一个人能坐到自己位置的概率是多少?
  • 扩展,第$K$个人能坐到自己位置的概率是多少?

解答

Solution给出的两个完全靠想的答案:

  • 因为最终只可能剩下第一个位置和最后一个位置,而且具有对称性,所以最后一个人坐到自己的位置的可能性是50%.
  • 当第$K$个人登机时, 第$2, \dots, K-1$个位置都是坐着人的, 其余$N-K+2$个位置中有一个被占,而且概率相等,所以第$K$个人的座位被占的概率是$1/(N-K+2)$.

自己的答案 很久之前做过这道题…当时应该是爆推公式,现在已经忘记了…又推了一遍,但感觉没以前那个版本复杂…

现在设$F(n,k)$是$N$个人登机,第$K$个人座位被占的概率,可得

化简得到

设$S(n,k) = F(n,k) + F(n-1,k-1) + \dots + F(n-k+2,2)$, 带入上式得到

化简得到

已知$F(n,k) = S(n,k) - S(n-1,k-1)$, 得到

化简得到

最终得到答案