Skip to main content

数学趣题:看电影

问题：有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。
Labels:

Comments

Post a Comment

Popular posts from this blog

Determine Perspective Lines With Off-page Vanishing Point

In perspective drawing, a vanishing point represents a group of parallel lines, in other words, a direction. For any point on the paper, if we want a line towards the same direction (in the 3d space), we simply draw a line through it and the vanishing point. But sometimes the vanishing point is too far away, such that it is outside the paper/canvas. In this example, we have a point P and two perspective lines L1 and L2. The vanishing point VP is naturally the intersection of L1 and L2. The task is to draw a line through P and VP, without having VP on the paper. I am aware of a few traditional solutions: 1. Use extra pieces of paper such that we can extend L1 and L2 until we see VP. 2. Draw everything in a smaller scale, such that we can see both P and VP on the paper. Draw the line and scale everything back. 3. Draw a perspective grid using the Brewer Method. #1 and #2 might be quite practical. #3 may not guarantee a solution, unless we can measure distances/p...
2 comments
Read More »

[转] UTF-8 and Unicode FAQ for Unix/Linux

这几天,这个东西把我搞得很头疼 而且这篇文章好像太大了,blogger自己的发布系统不能发 只好用mail了 //原文 http://www.cl.cam.ac.uk/~mgk25/unicode.html UTF-8 and Unicode FAQ for Unix/Linux by Markus Kuhn This text is a very comprehensive one-stop information resource on how you can use Unicode/UTF-8 on POSIX systems (Linux, Unix). You will find here both introductory information for every user, as well as detailed references for the experienced developer. Unicode has started to replace ASCII, ISO 8859 and EUC at all levels. It enables users to handle not only practically any script and language used on this planet, it also supports a comprehensive set of mathematical and technical symbols to simplify scientific information exchange. With the UTF-8 encoding, Unicode can be used in a convenient and backwards compatible way in environments that were designed entirely around ASCII, like Unix. UTF-8 is the way in which Unicode is used under Unix, Linux, and similar systems. It is now time to make sure that you are well familiar ...
Post a Comment
Read More »

Moving Items Along Bezier Curves with CSS Animation (Part 2: Time Warp)

This is a follow-up of my earlier article.  I realized that there is another way of achieving the same effect. This article has lots of nice examples and explanations, the basic idea is to make very simple @keyframe rules, usually just a linear movement, then use timing function to distort the time, such that the motion path becomes the desired curve. I'd like to call it the "time warp" hack. Demo See the Pen Interactive cubic Bezier curve + CSS animation by Lu Wang ( @coolwanglu ) on CodePen . How does it work? Recall that a cubic Bezier curve is defined by this formula : \[B(t) = (1-t)^3P_0+3(1-t)^2tP_1+3(1-t)t^2P_2+t^3P_3,\ 0 \le t \le 1.\] In the 2D case, \(B(t)\) has two coordinates, \(x(t)\) and \(y(t)\). Define \(x_i\) to the be x coordinate of \(P_i\), then we have: \[x(t) = (1-t)^3x_0+3(1-t)^2tx_1+3(1-t)t^2x_2+t^3x_3,\ 0 \le t \le 1.\] So, for our animated element, we want to make sure that the x coordiante (i.e. the "left" CSS property) is \(...
3 comments
Read More »