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

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


两道题都摘自《The Unofficial IEEE Brainbuster Gamebook: Mental Workouts for the Technically Inclined》，第一题稍有修改，以防个别同志写程序brute force。自己画的图，有点丑。 [吴永铮 (3-24 23:09, Long long ago)] [ 传统版 | sForum ][登录后回复]1楼

老大很强大，把5座桥改成了25座。。

还是谢谢你推荐的这本书！[Broadway (3-25 18:50, Long long ago)] [ 传统版 | sForum ][登录后回复]2楼

第一题比书上的原题难得多，因为有些通路会在某一段掉头往回走。好难啊。。。

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


[hash (3-26 0:02, Long long ago)] [ 传统版 | sForum ][登录后回复]3楼

(引用 hash:第一题比书上的原题难得多，因为有些通路会在某一段掉头往回走。好难啊。。。 记起一个类似的问题： 在W*L的纸上(W>>L)随机地撒火柴棍。...)我只是多画了几个桥，但解法和原题一样。你想复杂了[吴永铮 (3-26 0:50, Long long ago)] [ 传统版 | sForum ][登录后回复]4楼

第二题还是不清楚啊，是扔球时候的正下方，还是球落地时候的正下方？[香陵居士 (3-26 11:20, Long long ago)] [ 传统版 | sForum ][登录后回复]5楼

(引用 香陵居士:第二题还是不清楚啊，是扔球时候的正下方，还是球落地时候的正下方？)扔球时候的正下方那我再定义严密一点吧。

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

"A的正下方的地上"的意思是"过A和地心，作一条直线，这条直线和地面的交点"。当然A点不能在地面以下。交点有两个，肯定是近的那个咯。[吴永铮 (3-26 12:29, Long long ago)] [ 传统版 | sForum ][登录后回复]6楼

(引用 hash:第一题比书上的原题难得多，因为有些通路会在某一段掉头往回走。好难啊。。。 记起一个类似的问题： 在W*L的纸上(W>>L)随机地撒火柴棍。...)你说的那个火柴棍，就连简化为一维后也很难。假设火柴棍是随机放在一根筷子上的，问火柴棍完全覆盖筷子的概率。

与此相关的有个"random parking problem"。就是说在一条长为100的线段上随机放长为1的线段，这些长为1的线段不能有交集，一直放到不能再放为止，问期望可以放多少条。答案是70多条，没法用closed form表示，是用归纳法解的。二维的相同的问题是open problem。参见http://mathworld.wolfram.com/RenyisParkingConstants.html[吴永铮 (3-26 12:50, Long long ago)] [ 传统版 | sForum ][登录后回复]7楼

(引用 吴永铮:我只是多画了几个桥，但解法和原题一样。你想复杂了)书里给的答案算概率好像算错了...不过利用对称性是对的...没想到这个

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

[hash (3-26 16:15, Long long ago)] [ 传统版 | sForum ][登录后回复]8楼

(引用 吴永铮:你说的那个火柴棍，就连简化为一维后也很难。假设火柴棍是随机放在一根筷子上的，问火柴棍完全覆盖筷子的概率。 与此相关的有个"random ...)嗯，把那几篇文章找出来看了看，他们是用monte carlo来brute force[hash (3-26 16:22, Long long ago)] [ 传统版 | sForum ][登录后回复]9楼

(引用 hash:书里给的答案算概率好像算错了...不过利用对称性是对的...没想到这个 一直在考虑n*m座桥的问题，动态规划是行不通的。你又不让brute for)brute force行不通，因为2^(m*n)种情况，太多了也就只能用对称的方法解这种特殊情况，没法推广。[吴永铮 (3-26 16:31, Long long ago)] [ 传统版 | sForum ][登录后回复]10楼

(引用 hash:书里给的答案算概率好像算错了...不过利用对称性是对的...没想到这个 一直在考虑n*m座桥的问题，动态规划是行不通的。你又不让brute for)书上没错，注意P(A+B)可不是P(A)+P(B)P(A+B)=P(A)+P(B)-P(A*B)
有时也写成
P(A|B)=P(A)+P(B)-P(A&B)[吴永铮 (3-26 16:34, Long long ago)] [ 传统版 | sForum ][登录后回复]11楼

(引用 吴永铮:brute force行不通，因为2^(m*n)种情况，太多了也就只能用对称的方法解这种特殊情况，没法推广。)老大题目出的太吓人，弟兄们只好猜个0.5，或是到网上搜索找答案了。。[Broadway (3-26 18:25, Long long ago)] [ 传统版 | sForum ][登录后回复]12楼

(引用 吴永铮:书上没错，注意P(A+B)可不是P(A)+P(B)P(A+B)=P(A)+P(B)-P(A*B) 有时也写成 P(A|B)=P(A)+P(B)-P(A&B))我是说P(B), P(C)的表达式需要展开，才能用“since all prob. are the same”来下结论。[hash (3-26 20:32, Long long ago)] [ 传统版 | sForum ][登录后回复]13楼

(引用 吴永铮:brute force行不通，因为2^(m*n)种情况，太多了也就只能用对称的方法解这种特殊情况，没法推广。)Monte Carlo is the much better than simplistic brute force.[hash (3-26 20:34, Long long ago)] [ 传统版 | sForum ][登录后回复]14楼

(引用 Broadway:老大题目出的太吓人，弟兄们只好猜个0.5，或是到网上搜索找答案了。。)解不出来也可以参加讨论嘛第一题我也没想出来，我看答案才知道的。

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

这就是问什么我把它改成25座桥，以免谁有类似的想法。[吴永铮 (3-26 21:35, Long long ago)] [ 传统版 | sForum ][登录后回复]15楼

(引用 吴永铮:解不出来也可以参加讨论嘛第一题我也没想出来，我看答案才知道的。 我看到第一题后的第一反应就是，五座桥，只有32种情况。把32个情况全...)我也没有其他想法啊，只是想到利用对称性只用考虑一半的“入口”就可以了。[香陵居士 (3-27 12:58, Long long ago)] [ 传统版 | sForum ][登录后回复]16楼

(引用 香陵居士:我也没有其他想法啊，只是想到利用对称性只用考虑一半的“入口”就可以了。)除了你说的对称，还有另一种对称，dual graph[吴永铮 (3-27 14:14, Long long ago)] [ 传统版 | sForum ][登录后回复]17楼

(引用 吴永铮:除了你说的对称，还有另一种对称，dual graph)Do you mean isotropic in 2D?[Broadway (3-27 18:47, Long long ago)] [ 传统版 | sForum ][登录后回复]18楼

Technically Inclined[hahata (3-27 18:55, Long long ago)] [ 传统版 | sForum ][登录后回复]19楼

(引用 Broadway:Do you mean isotropic in 2D?)what do you mean by isotropic?[吴永铮 (3-28 1:04, Long long ago)] [ 传统版 | sForum ][登录后回复]20楼