数学建模(1)——小剧场入座问题

题目如下： > 小剧场一排有$n$个座位，由于各排之间空隙较小，如果某座位已有人入座，则入座者必须起身才能让后来者通过该座位。若一与会者进入会场时该排有若干个座位可供其选择，则他以相等的概率选择其中一个座位就坐。 > > 1. 若该排座位只有左侧一个入口，所有与会者一旦就坐就不愿起身让后来者通过。记$E_n$为该排最终入座人数的期望，试写出$E_n$满足的递推关系，并求$E_n$； > 2. 若该排座位左右两侧均有入口，所有与会者以$p$的概率起身让后来者通过，以$1-p$的概率不让后来者通过（如果与会者第一次选择了起身，则之后所有选择都是起身；如果与会者第一次选择了不起身，则之后所有选择都是不起身。即概率判定只有一次）。记$F_n$为该排最终入座人数的期望，试写出$F_n$满足的递推关系。 本题使用递推法求解，其思想在于，将入座过程划分为第一个人入座，和其他人入座的两个步骤。 对于第一小题，最简单的情况是，小剧场一排只有一个座位，即$n=1$，此时座位一定能容纳一个人，即$E_1=1$。如果$n=2$，则按照上述的划分步骤，第一个人可能以$1/2$的概率选择坐在第一个位置，这时候如果后面再有人来，后来者也不能坐在里面的第二个位置了；但第一个人也可能以$1/2$的概率坐在第二个位置，这时候后面如果再有人来，后来者还可以坐在第一个位置，所以 $$ E_2=\frac{1}{2}(1+2)=1+\frac{1}{2}. $$ 当$n=3$的时候，情况稍微复杂一些。如果第一个人坐在第一个位置，那么这排就不能再坐人，而如果第一个人坐在第二个位置，则这排一定能、也只能再容纳一个人。但如果第一个人坐在第三个位置呢？此时，这个人坐下之后，小剧场还有两个位置是能坐人的，但这两个位置不一定能坐下两个人（也许第二个人就坐在了第一个位置），此时我们不需要再讨论，因为我们已经计算过小剧场有两个位置能坐人时的期望$E_2$，因此我们能得到以下的算式： $$ E_3=\frac{1}{3}(1+2+E_2)=1+\frac{1}{2}+\frac{1}{3}. $$ 现在我们使用递推的思想来计算$E_n$，这意味着我们在计算$E_n$之前，$E_1,E_2,\cdots,E_{n-1}$都是已知的，并且规定$E_0=0$。现在，一排有$n$个座位，第一个人以$1/n$的概率坐在每一个座位上，当它坐在第$k$个座位上时，第$k$个至第$n$个座位都不能坐人，也就是只有前$k-1$个座位能坐人，这$k-1$个座位能坐下的人的期望是$E_{k-1}$。于是，我们得到以下的等式： $$ E_n=\sum_{k=1}^{n}\left[\frac{1}{n}\left(1+E_{k-1} \right) \right]=1+\frac{1}{n}\sum_{k=1}^nE_{k-1}. $$ 求解此式，有 $$ E_{n+1}=1+\frac{1}{n+1}\sum_{k=1}^{n+1}E_{k-1}=1+\frac{n(E_n-1)+E_n}{n+1}, $$ 即 $$ E_{n+1}-E_n=\frac{1}{n+1},\\ E_n=\sum_{j=1}^{n}\frac{1}{n}. $$ --- 第二小题与第一小题稍有不同，加入了两个变数：一是让摆放着以$p$的几率为“好人”（这样它每次都会让座），二是剧场的通道变成了两侧进入。第一个变化对题目造成的影响是，如果第一个进入的是好人，则此时还有$n-1$个座位是可用的；第二个变化对题目造成的影响是，如果第一个进入的人以$1-p$几率为“坏人”并坐在第$k$个位置上，剩余的可用座位除了前面$k-1$个外，后面的$n-k$个也是可用的。 依然用递推式给出结果，此时$F_n$满足的式子是 $$ F_n=\sum_{k=1}^{n}\left[\frac{1}{n}\bigg(1+pF_{n-1}+(1-p)(F_{k-1}+F_{n-k}) \bigg) \right]. $$ 此式难以解析给出，可通过计算机模拟给出$F_n$的近似数值。