What if beyond what-if —— Spiders vs. the Sun

不知道有多少读者朋友一样和我是知名网络漫画家 xkcd 的 what-if 系列的狂热爱好者(限于英语水平以及文化差异,他的漫画我经常get不到笑点)。这个系列的特点是用一些更加脑洞的方式回答一些已经很脑洞的问题。即使我自诩是一个脑洞很深的人,这个系列也常常让我叹服。最新一期的 what-if 是有人问,身边的蜘蛛的万有引力大,还是太阳的万有引力大?
作者先后比较了一只亚马逊食鸟蜘蛛对身边人的引力,整个地球的所有蜘蛛平摊在地球表面上对地表上的一个人的引力,以及一个长满了蜘蛛的废水处理厂对厂旁边的一个人的引力。尽管作者使用了三种不同的表达方式,但其实这三个力与太阳对地球上一个人的引力的大小相比并不是递进关系,它们与太阳对人造成的引力之间的倍数分别差了7个,13个,和7个数量级。然而一个自然而然的脑洞他却没有填上,那就是,全地球的蜘蛛能对一个人造成多大的引力?这个引力和太阳对人造成的引力相比呢?
于是我的脑洞迅速歪到了给定体积(当然还有密度)的物体,什么形状能产生最大的引力这个问题上。
这个形状首先肯定是一个相对合力方向旋转对称的形状。稍微思考一下就能够明白这个形状的外表面上任意一个质量元对于这个质点的引力在合力方向上的分量是个恒量。也就是说,\(\cos(\theta)/r^2\)是一个恒量。如图,这样的面事实上是一个6次曲面\((x^2+y^2+z^2)^2=c^4z^2\)。它比球体稍微要矮一些。

 

这个曲面内部的体积可以用球积分计算

\[\int_0^{2\pi}d\phi \int_0^{\frac{\pi}{2}}d\theta \sin\theta\int_0^{c\sqrt{\cos\theta}}r^2 dr=\frac{4\pi c^{3}}{15}\]
其中\(c\)满足\(r^2=c^2\cos\theta\),也就是这个长轴的长度。我们假设蜘蛛为了和太阳比较引力的伟大事业,都自觉自愿的被打成了蜘蛛酱,哦不,蜘蛛浆。那么,它们的密度可以用水来代替。xkcd相当不负责任的推算了一个\(2\times10^8\)kg的世界蜘蛛总量。那我们就要
代入上式等于\(2\times10^5\text{m}^3\),得到\(C_0\)等于62.04m。和人的平均身高大概差了30多倍,勉强算的上远远大于吧w
而每一个等\(c\)面上,每个体积元的引力加速度(就省的再乘个人的重量了)贡献都是\(\frac{dV\rho\mathrm{G}}{c^2}\)。由于\(r=c\sqrt{\cos\theta}\),故\(dr =\sqrt{\cos\theta}dc\) 。故整个形状对人的引力大小可以表示为

\[g_{\text{spider}}=\int_0^{2\pi}d\phi \int_0^{\frac{\pi}{2}}d\theta \sin\theta\int_0^{C_0}\cos\theta c^2\sqrt{\cos\theta}\frac{\rho G}{c^2}dc=\frac{4\pi\rho GC_0}{5}\]

\[=1.04\times 10^5\text{m/s}^2\]
远远小于太阳施加的引力加速度,也就是

\[6.67384\times 10^{-11}\times 1.989\times 10^{30}/(1.49\times10^{11})^2=0.0059\text{m/s}^2\]
其实上面这段计算根本就跟放屁一样没有任何意义,简单计算就知道这种形状也就比同样质量的球体多了1/3引力,而那个不靠谱的蜘蛛总量估计误差怎么想也比这大得多。
不过除了有趣的计算过程之外,我们还知道到底差多少了。由于那个加速度和\(C_0\)一次方成正比,所以大约\(C_0\)再大个600倍差不多就赶上太阳了。看起来也不多嘛。
根据这个页面的数据,地球上所有的生物干重大概在550000000000吨左右,湿重大概要乘以3,比起我们的要求还是差了30倍左右。
地球生物太弱了啊!
有这闲工夫去写论文啊!

棋盘上的越狱游戏

Youtube上面有一个很有趣的玩弄数字的频道Numberphile,最近它们发布了一个视频来解释一个很古旧的谜题的解法。这个谜题的规则很简单,问题看上去也很简单,可是当你去尝试解决的时候却会发现这货其实并没有那么简单,最有趣的是,这个最后看上去好像很复杂的问题其实只需要会四则运算就能解决,听上去是不是很好玩呢?如果你的英文还行,访问Youtube也没有障碍的话,现在就可以点击上面的链接去一探究竟。当然如果你懒,也可以听我在这里说,毕竟这就是这篇文章的目的。

首先你有一个国际象棋棋盘,这个想必大家都已经熟悉了:

dmv0102b

其次你有一堆圆形的像围棋一样的棋子,就不要吐槽为什么要在国际象棋棋盘上下围棋了,思路不广哪来的谜题呢。

至于规则也很简单:

屏幕快照 2013-12-25 下午1.06.17

首先我们在某一格里有一个棋子

屏幕快照 2013-12-25 下午1.06.25

然后我们在它的上面和右边各放一个棋子,最后把原来的棋子拿掉。游戏前进的方向就是绿色箭头指向的方向。

当然了,如果某个棋子的上面或右边已经有一个棋子了,那么我们就必须先将占位的棋子移走才能移动那个棋子。

好了,规则就是这么简单,问题也不复杂,我们现在有这么一个“监狱”,就是下图被圈起来的部分:

屏幕快照 2013-12-25 下午1.42.09

监狱里关着3个棋子,那么请问,使用上面的规则,我能让这个监狱里没有棋子吗?你可以现在就拿张纸画一画,然后再往下看。

.

.

.

.

.

如果你已经试过了,可能就会发现,这个棋盘不够用,那么我们就换个大点的,让这个棋盘向上向右都是无限延伸的,再来试一试。

.

.

.

.

.

好了,试到现在你的纸应该已经花到没法看的地步了,不过很遗憾,那个监狱里似乎还有人在里面。到现在大部分人应该都觉得,这个看上去很弱智的问题,是做不到的,那么下一步就变成了,如何证明这事是不可能的呢?证明做不到是个很麻烦的问题,在大部分情况下几乎是不可能的,Quora上面有这么一个讨论串 How is it possible to disprove the existence of anything with certainty? 说的就是这个问题。不过还好我们这里只是一个纯粹的数学问题,想要证明这是不可能的仍旧是可能的,并且很简单,当然,简单的前提是你知道怎么做_(:з」∠)_

证明的思路是,我们需要一个“不变量”,这个量在我每次做完移动后都是不变的。那么显然个数不行,因为每次移动都会一个变成两个,于是就给每个格子赋一个权重吧,然后让每个格子的权重等于其上面的和右边的格子权重的和,这样的话我移动一个棋子,移动前后其所处格子的权重是不会变的,就像这样:

屏幕快照 2013-12-25 下午2.09.23

那么给所有的格子都赋予一个权重并且满足这样的条件是可能的么?回想一下移动棋子的规则,每次移动棋子都会在其上方和右方放置一个新的棋子,这正好是是成对角线对称的形式:

屏幕快照 2013-12-25 下午2.09.37

而我们的棋盘正好也是对角线对称的!也就是说我只要给两个NEW赋予相同的值,让它们等于OLD的一半就可以了!

现在我们就可以给棋盘赋值啦,起始点当然是左下角,就给个最简单的,1好了,然后是两个最近的格子给1/2,像这样:

屏幕快照 2013-12-25 下午2.38.36

这样我们就可以将棋盘的每一个格子赋予一个权重了。好了,证明最困难的部分就到此为止了,后面的部分不过就是基本的演算了,有了这些,想必有不少人已经知道该怎么做了,是的,就像这样:

屏幕快照 2013-12-25 下午2.45.55

我们现在有一个带权重的棋盘,以及在左下角里的3个犯人,为了将他们移动出去,绿色区域的权重必须至少要等于监狱里的权重才行,因为无论做多少步移动,初始的权重是不会变的,而如果我能将所有的棋子移出监狱,那么他们最后呆在的绿色区域权重相加就必须等于监狱内的权重。可是如何算呢?这个绿色的部分也不是规则形状的,那么干脆就算整个棋盘的权重后减掉监狱部分的好了。即使这样,一个二维的数列看上去也很难算,那么干脆我们就从最下面一排开始吧,那么最下面一排的值就是:

S=1+1/2+1/4+1/8+\dots

这就是一个典型的等比数列了,如果上过初中的话应该都可以解决,不过之前说了,我们只需要四则运算就能解决这个问题,那么作为一个小学生,我们要怎么解呢?我们可以两边都乘上一个2来看看:

2S=2+1+1/2+1/4+1/8+\dots

咦,自2之后的那部分不就是之前的S么?好,那么我们就能写成:

2S=2+S

这就太简单了 S=2。 哇,我们居然用一堆无限的数加出了一个有限的值,是不是很有趣呢?如果你觉得有趣,那么稍微跑一下题,试试这个问题如何:

A=9/10+9/100+9/1000+9/10000+\dots

这里的A又等于多少?提示,你可以试着在两边同时乘以10来看看。那么这个跑题的部分先放在一边,回到棋盘的部分,如法炮制我们可以把每一行都加起来,最后的结果就是这样:

屏幕快照 2013-12-25 下午3.04.27

想必到现在你已经是老油条了,这个新的数列加法也不用我说什么了吧,答案就是4。好了,现在我们知道,监狱部分的权重是2,监狱外的权重和也是2,所以…似乎是可以的?可是别忘了,监狱外有无穷个格子,也就是说在有限步骤里是填不满的,也就是说,在有限的一盘游戏里,你是没法将监狱里的棋子全部移动出来的,也就是说,我们证明了这个游戏是不可能的。怎么样,这个看上去很简单的游戏是不是很有趣呢?

最后剩下一点,让我们回到跑题的那部分,想必你已经算出来了,A=1,不过我们把那堆加法的数字换个方法来写:

9/10+9/100+9/1000+9/10000+\dots=0.9+0.09+0.009+0.0009+\dots=0.99999999999 \dots

所以

0.99999999\dots=1

关于九宫格解锁的可能种数。

不知道有多少蛋疼如我的人每天在解锁手机的时候都忍不住想,这锁到底能有多少种呢?

这个问题并不像表面上看起来那么简单,至少不是9个点全部排列的9+9*8+9*8*7+9*8*7*6+9*8*7*6*5+9*8*7*6*5*4+9*8*7*6*5*4*3+9*8*7*6*5*4*3*2+9*8*7*6*5*4*3*2*1=986409。为什么不是呢?因为有些组合是无法达到的。对于一个九宫格解锁来说

1 2 3
4 5 6
7 8 9

像1->3->2这样的路径是不行的,但是反过来说,2->1>3这样的路径是可以的,也就是说,如果把一种锁当成是一串数字,那么每横每竖每斜两端的数如果相邻,就必须位于中间的数之后。

接下来的问题就简单了,穷举呗(谁用组合数学解出来了请务必和我联系)。判断的程序很好写(虽然挺多行,总之就是在一个数组里搜索13,17,19,46,28,37,79,39的组合,看它们是否在2,4,5,5,5,5,8,6之后)。排列穷举起来还是有点麻烦的,我是用链表+迭代解决的。

另外经提醒,由于4个点以下的密码是不允许的。总之,得出的结果是 382069。对这个结果我还是比较有信心的(之前那个迭代部分有误)。如果有兴趣的话,源程序在这里

我知道你不知道我知道你知道

技术宅结城浩写了几本Java,C,Perl的书后估计是觉得程序猿的钱不好赚,于是打起了宅们的主意,一本数学少女就这么红起来了。第一次听说这本书还是大一,听介绍还挺有趣的,可惜当时没有中文版,真正看到还是几年后的事了。前些日子听说这书居然还出系列了,并且还漫画化了,我该说11区已经没有救了么。看了漫画第一话的内容,居然是经典的泥孩子问题,上次说到的模态逻辑和可能世界理论正巧能够用的上,那么既然上次只是很简单的说了一下大概,这次借这个机会我就再多说两句好了。

泥孩子问题是这样的:

想象一下有n个孩子在一起玩,他们的母亲告诉他们如果他们弄脏了自己,后果会很严重。所以,理所应当的,这些孩子不愿意自己变脏,但是却非常乐意别人变脏(这腹黑的……)。现在,我们假设在这n个孩子中有k个在玩的时候弄脏了他们自己的额头,每个人都能看到其他人的的额头但是不能看到他们自己的额头。所以,没人会坦白他看到了什么。当然为了不至于回家后面对不知道是什么的“很严重的后果”,他们一起来到了父亲那里。这个父亲显然也不是省油的灯,他并没有直接告诉这些小孩他们头上有没有泥巴,只是说了“你们之间至少有一个人头顶有泥巴”。之后这个父亲就一遍又一遍的问“你们知道自己头上有泥巴么?” 我们假设所有小孩都足够聪明,诚实,并且他们总是同时回答,那么将会发生什么?

我们先假设只有3个孩子,那么如果我们用一个三元组(q_1, q_2, q_3)来表示这三个孩子的状态,以0或1分别表示某人头上没有或有泥巴,则我们知道所有的可能世界有8种:(0,0,0),(1,0,0),(0,1,0),(0,0,1),(0,1,1),(1,0,1),(1,1,0),(1,1,1)。如果我们把“0个孩子头上有泥巴”,“1个孩子头上有泥巴”,“2个孩子头上有泥巴”,“3个孩子头上有泥巴” 分成4组的话,我们可以画出下面的这副图M_0
Photobucket

其中每个点代表一个可能世界,这个可能世界的状态则被标注在旁边,那么边是按照什么规矩连接起来的呢?从数值上讲,是连接有且仅有一位与起始点不同的点,所以(1,0,0)可以连接(1,0,1),(1,1,0),(0,0,0)而不能连接(0,1,1)因为他们有3位不同而不是一位。从含义上来讲,由于某个点代表着一个可能世界,则和它连接的点就是这个可能世界的所有可能世界,但是这里稍微有点复杂,因为这些可能世界是从不同人眼里出发得到的可能世界。回到具体的含义上来,(1,0,0)代表了孩子A头上有泥巴而孩子B,C上没有,那么这个世界中,由孩子A看来,他知道B和C头上没有泥巴,但是不知道自己头上有没有泥巴,所以A的所有可能世界是(1,0,0)和(0,0,0)。同理,B的所有可能世界则是(1,0,0)和(1,1,0),C的就是(1,0,0)和(1,0,1)。

那么为了明确区分到底是谁眼里的可能世界,我们在每条边上对此做出标示,则这个图就可以变为M_1
Photobucket Pictures, Images and Photos

所以在他们的父亲说任何话之前,所有可能世界和他们的关系就如上如图所示。但是,当父亲说:“你们之间至少有一个人头上有泥巴”的时候这些可能世界就发生了变化,(0,0,0)变成不可能的了,所以就成了这样,图M_2
Photobucket Pictures, Images and Photos

此时,如果只有一个孩子头上有泥巴,那么头上有泥巴的那个孩子则必然知道自己头上有泥巴,而另外两个孩子则仍没有足够的信息来确定是否自己头上有泥巴。为什么呢?我们假设此时的世界是(0,0,1)那么以这个世界为基准,对于A而言虽然他不知道自己所在的世界,但是通过观察其他的两个孩子,他可以知道自己必定在(0,0,1)和(1,0,1)这两个世界其中之一,但是这两个世界里A头上有没有泥巴是不一样的,所以A无法判定自己头上有没有泥巴,B同理。唯独C在这里除了(0,0,1)外不存在其余的可能世界,所以对于C而言,他可以确定自己头上一定有泥巴。到这里,我们可以说,如果孩子们可以判断在所有可能世界里,自己头上有没有泥巴这件事情况都是一样时,他就可以确定自己头上有没有泥巴了。

那么数学上我们如何表示?在这里我们最终要推出的是A,B,C知道自己头上有(或没有)泥巴,于是如果我们用p表示自己头上有泥巴,q表示自己头上没泥巴,那么p,q就是我们常说的命题(一个能区分真假的语句),K_AK_BK_C分别表示A,B,C知道,我们把它们叫做模态算子。则K_A p的含义就是A知道自己头上有泥巴,如果我们再加入\lnot来代表否定,那么K_A \lnot K_B p就表示A知道B不知道自己头上有泥巴。当然这么下去也可以造出像标题一样绕口的句子,不过把人绕晕乎是没有任何好处的,就在此打住。所以上面提到的(0,0,1)世界的情况,我们就可以写为:

  • $$(M_2, (0, 0, 1))\models \lnot K_A p$$
  • $$(M_2, (0, 0, 1))\models \lnot K_B p$$
  • $$(M_2, (0, 0, 1))\models K_C p$$

这些式子的含义是,在图M_2所示的情况下,当世界为(0,0,1)时,A,B,C三者的知识情况,言下之意就是当世界为(0,0,1)时,A,B一定不知道自己头上有没有泥巴,而C一定知道自己头上有泥巴。

回到最初的问题,如果世界不是(0,0,1)而是(1,0,1)呢?(M_2, (1, 0, 1))又能得到什么?此时我们可以看到,无论是A,B,还是C,在(1,0,1)这个世界下,对于他们自己的总有另一个可能世界,在那个可能世界中自己头上有没有泥巴是不一样的,所以要是这样,他们都不会知道到底自己头上有没有泥巴,于是三人都会回答:不知道。这时情况又起了变化,当所有人回答不知道时,这就意味着必定存在着两个或两个以上的人,他们头上有泥巴,于是这个世界又变成了M_3:
Photobucket Pictures, Images and Photos

此时,除了对于B而言还存在两个可能世界以外,A,C均只有一个可能世界,所以在图M_3的情况下我们有:

  • $$(M_3, (1, 0, 1))\models K_A p$$
  • $$(M_3, (1, 0, 1))\models \lnot K_B p$$
  • $$(M_3, (1, 0, 1))\models K_C p$$

那么,当世界是(1,1,0)时也可以“同理可得”,就不用多说了吧。如果你对这些感兴趣,可以另外参考MIT出版的Reasoning About Knowledge,上面说的很详细,当然数学上也要严谨的多。

TNND,回头看这文的时候突然反应过来,这泥马的拿手摸一下不就知道有没有泥巴了,还弄得这么麻烦,搞数学的还真是没事干啊。

海盗分金问题

但凡对趣味数学有兴趣或者接触过数学竞赛的童鞋们很可能听过这个问题。这个问题大约就是m个海盗,编号1-m,从第m个开始,对一些财宝提出分配方案,然后对方案进行表决,通过就分,通不过就把第m个海盗杀掉,让第m-1个海盗分,以此类推。假设所有海盗都极端理智,你是最后一个海盗,你该怎么提出方案才能保命并且收益最高?

大约我就记得这么个规则,然后有些细则记不大清楚了,这样容易出现多重解,于是就又自己加了一些细则(不过加了还是会有多重解,但是没有更合理的细则可以加了):

1.表决方式是过半同意方可通过,即2m个海盗中必须有m+1个同意方可通过

2.海盗们很腹黑,收益不变的情况下总是希望看到死人

3.财宝有相等的n份,这个n足够大

很明显这是个需要递推的问题,设第m个海盗为Am,我们从2个人开始研究,很明显2个人的时候无解,因为腹黑假设,A2即使把财宝全数送上也无法保命;3个海盗的时候,利用第A2的这种心理,A3大可以全吞所有财宝,因为A2无论如何都不能进行到2人表决。于是分配方案可写为

0,0,n

A4除了自己之外还需要争取2票,A3欲壑难填因而果断放弃,只要能让A1A2收入比三人的情况有所增加即可,于是给他们各一份,方案为

1,1,0,n-2

A5需要争取的也是两票,除非砸下血本(n-1份),否则拉拢A4无异于天方夜谭。于是放弃A4,A3只需要1份财宝即可拉拢,A1和A2中挑一个拉拢就行了(所以多重解了),方案为

2,0,1,0,n-3

0,2,1,0,n-3

A1A2都有可能得到2份,所以他们的行为很难预测,但是原则上说只要A6在方案中给他们稳定的2份,就必然得到支持,俗话说,a bird in the hand is better two in the bush,何况是两只鸟,作为A6,要获得3人支持,当然不可能去拉拢A5,A4是0个只需要1个即可拉拢,拉拢A3需要2个,拉拢A1A2都只需要2个。于是又是一个多重解。

0,2,2,1,0,n-5

2,0,2,1,0,n-5

2,2,0,1,0,n-5

大约就是这样可以分析到银河的尽头,我也懒的做了,但是以这个简单的数学模型去理解一些事情,你会发现无比精准:

为什么共产党要“依靠贫农,联合中农,限制富农,剥夺地主财产”,贫农(方案中得0份财宝的)非常易于收买,地主(Am-1)完全无法收买只能完全剥夺财产。用这个理解土地革命非常简单易懂。革命者要做的就是提出一个革命方案,分配利益,得到足够多人支持就可以推翻即得利益者了。这个高度抽象而有趣的数学模型让我进一步厌恶起了革命,对暴力的无所谓的应用很有可能制造的是下一个暴君。即得利益者被剥夺权力后其财产如果也被立刻剥夺,很有可能造就的就是另一群即得利益者,所以财富的平均只能是一个渐进的过程才能保证有序,这是俄罗斯正在发生的,也是中国终有一天要面对的。

当然我想说的其实已经说完了,严谨期间把通解做出来了:最末尾三个人的分配方案必须为1,0,X,其中X为收买人心之余的所有财宝。这个很好理解,地主要打击,贫农要依靠,利益要独占,很简单,很简单。前面的需要至少拿到一半的票,可以证明前面的那些人完全没有区别,都是收买要且仅要2份财宝的,可以随便选一些人收买。用数学归纳法证明,显然对于m=5是成立的,设m个海盗时成立,在m+1个海盗时,后三位如前所述是1,0,X,还需要一半以上的票,剩下的这个人包括m个海盗时的那个随机的多重态,这部分海盗收益的期望要么等于1(m-3为偶数),要么略大于1(m-3为奇数),再加上m个海盗时Am-2那个1,在m+1个海盗时收买起来都是要且仅要2份的(1份不够,由腹黑假定),这m-2个海盗也需要收买1半以上,证明完毕。之后可以计算出m个人总共需要的安抚份数是[m-2]+1份,[]为下取整符号,要是总共财宝不能分成这么多份,那么第m个海盗就死定了,能分的话,除了这些财宝有多少就能拿多少。还有我的前两个假定改一下解也会变,首先是腹黑假定一改就会产生平庸解——所有财宝集中于分配者,m=3成立,m个海盗成立时m+1个海盗不满于分配条件的只有第m个海盗,他的利益受到了损害,其他人都抱着事不关己的态度同意的话Am+1也可以侵吞所有财宝。至于表决时不需要超过一半只需要达到一半,即2x个人只要有x个同意即可,那么得出的解为一个很简单的;

0,X

1,0,X

0,1,0,X

1,0,1,0,X

0,1,0,1,0,X

以此类推,像国际象棋盘一样01交错即可