2007-03-20

数学趣题:看电影

问题:有N个人去看电影,其中有一个是疯子。每个人各有一张票,电影院恰有N个座位。N个人依次入场,疯子最先冲了进去。
疯子首先在N座位中随机(等可能)挑一个坐下,以后每个人进去后,如果自己的座位没有被占,则就对号入座,否则在现有的空座位上随机(等可能)挑一个坐下。
问最后一个人对号入座的概率


解法1
设所求为P(n),现将N个人按入场顺序编号为1-N,则1号为疯子。再把他们各自对应(按手中的票计)的座位也相应标为1-N。现考查1号
如果1坐到自己的座位上,这有1/N可能,则以后每人都回对号入座
如果1坐到N号最为上,则N不可能对号入座
如果1坐到i(1<i<N)号座位,这也是1/N的可能,则以后2至i-1号都会对号入座,此时把1号座位对应于i,这时就转化为了N-i+1个人的看电影问题,因此最后一个人对号入座的概率为P(N-i+1)

综上可知P(N)=(1 + sum(i from 2 to N-1) P(N-i+1) ) /N
可算得P(N)=P(N-1)=...=P(2),而对于两个人的情况显然所求为1/2,所以这就是最终结果

解法2
编号同上,对每一种N个人都坐下后的结果,我们把1-N号座位上的人的序号依次排开成一个数组,则如果都对号入座,应该是(1,2,...N)
容易看出N不是在最后一个就是在第一个,否则,设N在第i(1<i<N)个,则由于i比N先入场,i进场时他的座位一定是空的,这就矛盾了。
把所有的数组按照N的位置分为两组,并构造一个双射
对一个N对号入座(即N在最后一个)的数组,我们考察第一个数,设为i,那么我们说i+1至N这些人都对号入座了。如果这样不好理解,我们换种说法,即找 到“按进场顺序,最后一个坐错的人”,或不在自己座位上的序号最大的人,如果所有人都对号入座了,则把1号挑出来。这样,类似上面的分析,可知这个人一定 是坐在了1号座位上。
现在我们把这个数组中首尾对调一下,即最后一个坐错的人和N。得到了一个N没有对号入座的数组。把这个数组与原来的对应起来,易知这是一个双射,而且出现 它们的概率相同。因为1至i-1(i为与N交换的那个数)的座位在两边都一样,则出现概率也一样,i-2至N-1应该都是对号入座,是确定的。不同之处在 于i是坐了1号还是N号,根据题意,这时等概率的。
这样就知道了N对号入座的集合的概率和N没有对号入座的概率是相同的,那么显然为1/2。

No comments: