第一题:过河
见下图。这条河里有12个小岛，有25座桥连接小岛与小岛，小岛与河岸。每座桥都有0.5的概率是断开的。（比如那种可以拉起来以便过船的桥。）每座桥断开与否是独立的事件。问：在任意一个时间点，可以过桥的概率是多少？
注意这里问的是时间点，或者说以很快的速度过桥。所以“走到一个小岛上，等一会儿，再到另一个小岛上“是不允许的。

第二题:自由落体
在赤道上，从高楼上扔下一个球，不计空气影响。问这个球是不是落到正下方？偏东还是偏西？如果你要我定义什么叫正下方，有很多方法定义，比如拉根线掉个重锤，比如与地心的连线，这都是等效的。


两道题都摘自《The Unofficial IEEE Brainbuster Gamebook: Mental Workouts for the Technically Inclined》，第一题稍有修改，以防个别同志写程序brute force。自己画的图，有点丑。

把5座桥改成了25座。。

还是谢谢你推荐的这本书！

好难啊。。。

记起一个类似的问题：
在W*L的纸上(W>>L)随机地撒火柴棍。单位面积里火柴棍数量是均匀而已知的，但是方向是随机的。当然，我们排除火柴棍树立起来的情况。求火柴棍构成一条能跨过纸面（L方向）的通路的概率。
前一两年还有人发表论文讨论这个来着，只是把火柴棍换成碳纳米管。

那我再定义严密一点吧。

在赤道离地100米高处，释放一个小球。问小球是不是落到释放小球那一点的正下方的地上。

"A的正下方的地上"的意思是"过A和地心，作一条直线，这条直线和地面的交点"。当然A点不能在地面以下。交点有两个，肯定是近的那个咯。

假设火柴棍是随机放在一根筷子上的，问火柴棍完全覆盖筷子的概率。

与此相关的有个"random parking problem"。就是说在一条长为100的线段上随机放长为1的线段，这些长为1的线段不能有交集，一直放到不能再放为止，问期望可以放多少条。答案是70多条，没法用closed form表示，是用归纳法解的。二维的相同的问题是open problem。参见http://mathworld.wolfram.com/RenyisParkingConstants.html

不过利用对称性是对的...没想到这个

一直在考虑n*m座桥的问题，动态规划是行不通的。你又不让brute force...

也就只能用对称的方法解这种特殊情况，没法推广。

P(A+B)=P(A)+P(B)-P(A*B)
有时也写成
P(A|B)=P(A)+P(B)-P(A&B)

弟兄们只好猜个0.5，或是到网上搜索找答案了。。

来下结论。

第一题我也没想出来，我看答案才知道的。

我看到第一题后的第一反应就是，五座桥，只有32种情况。把32个情况全部画出来，一个一个数，有几个走得通的。

这就是问什么我把它改成25座桥，以免谁有类似的想法。