Matrix67: My Blog

假如宇宙是有界的……

Matrix67 — Thu, 20 Nov 2008 00:02:29 +0800

看完Proofs from THE BOOK的几何部分，我决定把书又放一放，开始阅读Infinity and the Mind。我承认我不该在当代文学史课上读这本书——读到第15页时，我看到了一段非常有趣的文字，竟然在课堂上放声大笑出来。不知道大家之前是否见过这个“思维实验”，我好像是第一次见到，它真的好搞笑。
历史上，不同的人对宇宙空间有着不同的见解。古罗马哲学家Lucretius认为，宇宙是无限的。让我们来看一看他的经典论证。假设宇宙是有限的。我们往宇宙的边界投掷一根标枪。则我们将看到以下两种情况之一：这根标枪穿过边界飞向远方，这说明宇宙并无边界，它是无限的；或者这根标枪一头装上宇宙边界停了下来，这说明边界外“有东西”挡住了标枪，同样说明宇宙是无界的。

Update: 其实我想说的是，笑点不是古人的论证与现代科学的差距，而是论证自身用到的二难性所带来的滑稽效果与逻辑推理出奇宏大的力量；正如证明上帝不是万能的（上帝能否创造一块连自己也举不起来的石头），或者大球小球落下去的速度一样快之类的思维实验，它们总是让人会心一笑。

无限长的金属杆：理想模型带来的悖论

Matrix67 — Wed, 19 Nov 2008 00:44:47 +0800

有些时候，数学模型和物理世界相结合可能会得出一些不可思议的悖论，Gabriel喇叭就是最经典的例子。这里，让我们来看另一个有趣的例子。

假设有一个无穷大的桌面，上面垂直地树立着一根有限长的金属杆。在这根金属杆的顶端用铰链连接一根无穷长的金属杆。这根无穷长的金属杆可以绕着活动关节处上下转动。让无穷长的金属杆随重力自由活动。注意到夹角α绝对不可能小于90度，因为我们的金属杆和桌面都是理想刚体，它们不能相交、穿透。这样的话，α只可能是90度。于是，荒唐的一幕发生了：这根无穷长的金属杆平行地悬在桌面上空，但却只有端点处这一个支撑点。

来源：http://www.cut-the-knot.org/WhatIs/Infinity/InfiniteRod.shtml

Steffen可活动多面体

Matrix67 — Mon, 17 Nov 2008 00:40:16 +0800

    大家都知道，三角形具有稳定性。如果你把三根木条钉成一个三角形，则这几根木条是不能活动的。这是因为，根据三角形的SSS全等判定法则，两个三角形的三边长对应相等，则这两个三角形一定全等。但四边形就不是了，用四根一样长的木条钉成一个正方形，握着相对的两个角往两边一拉，正方形就变成菱形了。不知道大家想过没有，类比到三维空间中，多面体的稳定性又是怎样的呢？
    Cauchy定理指出，如果两个凸多面体对应的面全等，那么这两个多面体全等。这告诉我们，任何一个凸多面体一定都是不可活动的。在Cauchy定理中，“凸多面体”这一条件是必需的。如果允许凹的多面体存在，对应面相等但整个多面体不全等的形状可以很轻易地构造出来。例如，想象立方体的某个面中心有一个小金字塔，这个金字塔既可以是向外凸的（就像表面上的一根刺），也可以是向内凹的（表面上的一个坑）；这是两个截然不同的多面体，但它们的对应面都是相等的。不过，这与我们的稳定性并没有关系，因为它并不是做连续的变形，而是直接一下就“跳”过来了。
    很长一段时间，人们曾经猜想，不存在可以做出连续变形且保持所有面不变的“可活动多面体”(Flexible Polyhedron)。1978年，Connelly找到了第一个反例。他给出了一个由18个面组成的可活动多面体。

Proofs from THE BOOK的第12章给出了Cauchy定理的一个非常精巧的证明，并在这一章末尾给出了一个更加简单的可活动多面体（上图），它是由Klaus Steffen构造出来的，只含有14个面和9个顶点，现在已经证明是“最简单”的可活动多面体。如果你按图中所标注的比例裁剪一张展开图，拼接成一个多面体的话，你可以捏着它的一条棱拽来拽去的玩。

你猜怎么着？我还就真做了一个！我把这个pdf文件打印在了一张稍微硬一点的纸上，然后按图示粘贴成了一个可活动的多面体。标了黑线的地方应该往外折，蓝线则应该往内折。做好后捏在手里玩了一下，嘿，还真他妈的可以动！

（官方消息）正式宣布本人脱光公布情侣Blog

Matrix67 — Sun, 16 Nov 2008 03:41:41 +0800

历经四年多的单身生活后，本Blog经常提到的，在我们系我们年级的一个和我纠结了大半年的，被我称为古汉MM的，最近几乎每篇日志下面都会以“燕仰”为名留下评论的MM，半个月前正式和我走到了一起。在学术方面，古汉MM和我几乎是两个极端，我们俩最终能走在一起真是一个奇迹。她在文学方面是一个巨牛，今后我亲爱的她将会在www.matrix67.com/yanyang写一个文学随想类的Blog，希望大家能够喜欢并帮忙宣传。不管最后结局如何，这个Blog都会一直更新下去。
好啦，废话不多说了，大家开始疯狂留评论吧……

Update: 承诺在下星期内向大家交代详情，并在再下周发pp

漫话二分（上）

Matrix67 — Thu, 13 Nov 2008 22:34:37 +0800

二分思想真的是无所不在，即使在中文系的专业课中我们也能见到这个词。在语言学概论中我们提到，一个音位可以由一组区别特征确定下来，这些区别特征总是以只具有“是/否”、“有/无”等两种对立属性的“二元偶分组”形式存在，因为这样可以最方便最快捷地确定出一个元素。这有点像猜数字一样，我想一个数字后让你来猜，我告诉你你的猜测是大了还是小了。只是在这里，回馈的信息不再是大小，而是“辅音/元音”、“口音/鼻音”、“浊音/清音”、“送气/不送气”等形式逐层细分。这让人联想到5张卡片猜年龄的老把戏，一系列火星的称球问题，基于比较的排序算法的复杂度下界，或者经典的20q在线游戏。
一个有趣的事实是，相当多的人都错误地理解了“二分”这个词，但他们在生活中却拥有很强的二分意识。我们语言学概论的老师（这里就不说是谁了）在讲解二分时举了一个甚为荒谬的例子：如果你要在房间里找一根针，那么你可以把房间划分为两半，如果这一半找不到的话说明针一定在房间另一半，此时再把那一半分成两部分，不断分分分分分最后总能找到针的位置。这是这位老师无数荒唐的例子中的冰山一角，因为这个“二分”与搜索别无二致。这个“二分”的判断环节并不是即刻返回的，而且最关键的是它并不具有规模减半的功能，或者说一旦返回“真”后我们并不会再接着二分下去。如果让我来举例子的话，同样是拿找东西打比方，在合唱队中找出跑调了的人是一个绝佳的例子，因为在合唱中我们能轻易分辨出一个不和谐的声音（虽然无法准确判断这个声音是从哪儿传来的），不断叫当前的人的其中一半来合唱便可渐渐判断出那个人的位置。但讽刺的是，这老师在举这个错误例子的同时，竟然在不自觉地用二分法来调整课件的字号。他发现这一页ppt的字号太小了，我们可能看不清，于是希望让字号尽可能的大但又不致于大到显示不下。他开始尝试40号，发现字已经超出屏幕了；然后把字体改成20号，又觉得还能再大一些；进而又改到28号（工具栏上的字号调整以4为步长），最后确定到了24号字。

如果真的叫一个课讲的好的老师来说二分，课程可以变得相当有意思。每次回我们高中时我都讲了很多次课，我最喜欢聊到的话题之一就是二分。从猜数游戏引入二分查询有序队列中的指定元素，然后提出一些标准的有序队列二分搜索的实际应用，比如解方程x^x=100一类的问题。紧接着提出二分的各种有趣的变形，例如如何在有序整数序列中查询A_i=i的元素。提出这些问题的目的就在于告诉大家，二分的思想不仅仅是用在猜数游戏一类的情况下。二分判断并不只限于“比目标值大/比目标值小”，只要能判断出目标值在哪边都行，例如在这里，A_i<i表明目标元素一定还在右边，A_i>i则表明目标元素在左边。

i = 1 2 3 4 5 6 7 8 9 10 A_i = -100 -20 -3 0 2 6 13 14 27 298

另一个经典的变形则是分段有序队列中的二分查询。假如有这么一个数列，它可以分为前后两个部分，两段各是一个递增数列，并且后一段的最大值比前一段的最小值还要小。比如说，数列12, 15, 19, 3, 6, 7, 9, 10就是这样一个数列。这相当于是一个有序数列循环移动之后的结果。如何在这个数列中查询指定的元素呢？事实上，这种“有序序列”虽然经过了变形，但丝毫不影响二分法的应用，因为我们依旧能判断出目标值在当前值的哪一边（这是很显然的，我不多解释了），这就已经足够了。
不结合实际应用的话，这些似乎没有实用价值的理论会变得乏味。其实，只要仔细思考，生活中对应的现象总是有的。我的秘方就是，想不出例子就想MM，爱情的复杂性保证其蕴含了各种千奇百怪的数学模型。一想到爱情，分段有序队列就能用上了。不妨为恋爱前后的“愉悦程度”建一个简单的模型：在恋爱之前，你会为找不到MM而越来越难过；一旦开始热恋愉悦值瞬间达到极大；之后热情会慢慢减小，但愉悦值始终比恋爱前要大。好啦，如果你想出一道题的话，问题背景已经是现成的了，不妨再定义一个符合这个模型的且不能直接解出来的分段函数，编几句形如“科学家发现恋爱前的愉悦值以a减某某某的速度递减，恋爱后则变为曲线a加某某某”的话，然后就来看看有多少人还能想到二分法吧。一般说来，好的题目背景起到了一个很强的干扰作用：题目背景越顺理成章，问题描述越是简单，看清问题背后隐藏的算法障碍就越大。另外，如果你给的函数巧妙到还需要大家先证明它的单调及有界，那这题目就真的绝了。

    要比谁的题目更绝，那绝对比不过USACO。USACO月赛中的二分题是真牛B了。我对二分的热情是相当的高。为高一高二的几个人备战省选时，我出了好几套模拟题，前面四套题每套都有一道来自USACO月赛的二分题。这个二分题是越来越诡异，以至于大家越来越难看出这套题里面哪道要用二分了。
    第一套题里的二分题是一个简单题：把一个长为N的数列划分为M段，要求每段数之和的最大值最小。例如，把100 400 300 100 500 101 400分割成5块，则100 400 | 300 100 | 500 | 101 | 400是最优方案之一，最大值500已经不能再小了，这个题一看就知道是二分后贪心判断，“最大值最小”之类的关键词几乎成了二分题的信号灯。像什么最小权值最大的完全匹配、瓶颈生成树问题（求最大边最小的生成树：二分后判断连通）、寻找权值波动最小的路径（找一条从A到B的路径使得所经过的边的最大权值和最小权值相差最小：枚举下界二分上界判断连通，滑动窗口更好），都是二分的经典问题。
    第二套题中的二分也是“最大值最小”类的问题，只是要更复杂一些：在带权无向图中，选择一些边使得A、B两点连通，要求费用最小。费用是这样算的：先从图中选出K条边（K值是给定的），免费；然后从图中选择其它你需要的边，费用为这些边的最大权值。这个题里，选边过程的先后顺序有一个很强的误导作用。事实上，正确的算法应该是先二分这个最大权值，再来判断把K条免费边的机会用上能不能把A、B连通，换句话说就是要想把A、B连通还差的边数超没超过K。当时做这个题时，不少人二分法是想到了，但却怎么也想不到该如何计算最少还需要多少条边才能连通A、B两点。其实方法很简单，把不超过当前二分出来的那个“最大权值”的所有边权值设为0，其它边的权值设为1，然后找一下最短路就可以了。
    第三次的二分题就不容易看出来了。给定一个有向图，每条边都有两种权值，时间和愉悦值。叫你寻找一条回路（不经过重复的边），使得愉悦值之和与时间总和之比最大。能想到这个题目是二分的话，那就真的很厉害了。二分最优比率C，然后给每条边设置一个新的权值，它等于C倍的时间减去愉悦值，再来判断是否有负权回路。这是怎么来的呢？不妨这样来看：对于任意一条回路，所求比率等于(Σ愉悦值)/(Σ时间)。如果二分出来的最优比率C偏小了，那说明满足(Σ愉悦值)/(Σ时间)>C的回路多得是，移动一下便有C*(Σ时间)-(Σ愉悦值)<0，即在新的权值设定下存在负权回路。如果没有负权回路的话，说明所有回路的比率都比C小，这就说明我们的C取大了。同样的思路也可以用来解决最优比率生成树问题。

    第四次的二分题可就是真的牛B大发了。假设有一个长度为N的数组A_i，里面的每个数都不一样。但是呢，你不知道数组里的数是多少。给出若干个形如“从A_i到A_j中的最小值是x”的命题，问你第一个和前面有矛盾的命题在哪里。例如，给你四个命题：A_1到A_10的最小值是7，A_5到A_19的最小值是8，A_3到A_12的最小值是5，A_11到A_15的最小值是4。第三句话显然是错的，否则前两个区间中至少有一个的最小值也达到了5。
    这个题难就难在，我们需要挖掘出“矛盾”的本质。究竟每一条命题给我们带来了什么信息呢？假设我告诉你，A_1到A_10的最小值是7，你仍旧不能推断出任何一个数，但有两点是肯定的：第一，这10个数里有一个数字7；第二，这里面的每个数都不能小于7。假设我们再给出一个A_5到A_19的最小值是8呢？此时，我们得知A_5到A_19里面有一个8，并且A_5到A_19的所有数都不小于8。注意！此时从A_5到A_10这一段中的数字下界升级了！由此得到启发，这些条件给出的信息说穿了就是每个位置可能出现的数的下界，它就是覆盖它的那些区间中的最大值。我们可以把区间端点排序，从左到右扫描一遍，用堆不断更新当前的最大值。在确定完每个位置可能的最小数后，我们开始寻找一个满足这些条件的解。由于数组中没有相同的数，因此对于所有回答“最小值为x”的区间，x必需出现在它们的交集中。如果这个交集为空，或者交集里面所有的位置（因下界过大）都不能取这个数，那么我们就可以肯定地说这一组条件是有矛盾的。如果我们顺利地给每个区间都安排好最小值所在位置，这立即说明了该组条件没有矛盾，因为我把其它那些没确定下来的位置取到无穷大，满足全部条件的数组就构造出来了。于是，我们有了一个O(nlogn)判断一组命题是否有矛盾的算法。
    这个题有趣就有趣在，上述算法虽然高效，但却只能判断命题组是否矛盾，不能检测矛盾首次出现的位置；而在线判断命题是否矛盾（一个命题一个命题地往里面加）反而要慢些。于是呢，二分答案就派上用场了：二分前面的无冲突命题的最大长度，然后用上面的O(nlogn)算法来判断看是不是有矛盾。

然而，上面这些二分题都还太“正统”了一些。拼完了NOI之后，我便在网上自由潇洒地学习各种自己感兴趣的算法，看到了不少真正另类而绝妙的二分……

祝各位网友节日快乐

Matrix67 — Tue, 11 Nov 2008 17:13:58 +0800

    初中的时候，有一天，老师问：你们最喜欢的数字是什么呀？
    一个同学说，我最喜欢的数字是1，因为1是第一的意思，我妈妈告诉我我要永远争第一。
    第二个同学说，我最喜欢的数字是11，因为我喜欢足球，足球需要全队11个人齐心协力。我希望我能够从足球中学会团队合作。
    第三个同学说，我最喜欢的数字是111，因为我喜欢指环王，我要像比尔博·巴金斯那样生活，在人生的111年里勇于探索，敢于挑战。
    然后呢，偏偏就轮到我了……
    我说，对不起，我有事先走了。

既然我的那个事情还没有公开，姑且就让我再过一下节日嘛~~

经典证明：不用数学归纳法直接推导平面图的Euler公式

Matrix67 — Sat, 08 Nov 2008 18:11:26 +0800

把《三体II黑暗森林》看完后，又把上学期已经放下的Proofs from THE BOOK拿出来翻了几页。当结束了数论部分进入几何学时，一些离散性的东西让整本书陡然科学了起来。前面那篇日志里的牛B证明就是我从这本书的第9章中看到的，运用线性代数的基本定理我们居然可以证明一个无从下手的图论问题！今天我又看到牛B证明了：平面图Euler公式V+F=E+2的非数学归纳法证明。以前我见到过各种Euler公式的证明，证明方法千奇百怪，其中不乏很多独具匠心的精巧证明，但它们本质上都是运用数学归纳法不断拆边重组减低规模，将复杂的平面图一点一点变得简单。在Proofs from THE BOOK的第11章，我见到了一个用半页纸写下的巧妙证明，证明方法简单、美观而有趣，读后让人会心一笑。

在介绍这个证明之前，让我们先来回顾一下什么是Euler公式。Euler公式是说，在一个由若干顶点和它们之间的一些不相交的边所组成的图中，等式V+F=E+2总成立，其中V表示顶点个数，E表示总的边数，F表示这个图分割出来的区域个数（包括一个“外部区域”，例如一个圆把平面分割为两个区域）。如图1，这个图共有6个顶点、10条边和6个区域，可以看到6+6=10+2是成立的。为了证明这个结论，考虑这个图的任意一个生成树（图1中加粗了的边）。再考虑这个图的“对偶图”：新图的每个顶点代表原图的一个区域，原图的两个区域相邻则在新图上的两个对应顶点之间连一条边（图2中的虚线部分）。接下来，我们找出原图中那些不属于生成树的边界线，把它们在新图中所对应的边加粗（图2中的加粗虚线）。容易看出，加粗的虚线是连通的，因为原图的粗线条是一棵生成树，它没有隔离出任何一块区域；同时呢，加粗虚线是没有环的，否则它将把某个原图的顶点包起来，从而原图中的加粗线条就不可能是生成树了。只需要注意到一棵树的顶点数等于边数加一，我们的结论就直接出来了：原图的顶点数就是Euler公式中的V，它等于原图生成树的边数加一；新图的顶点数就是Euler公式中的F，它等于新生成树的边数加一；而两棵生成树的边数总和正好就是原图中的E。于是呢，我们就得到了V+F=E+2。

趣题：完全图K_n最少可以拆成多少个完全二分图？

Matrix67 — Thu, 06 Nov 2008 23:57:55 +0800

一个完全图K_n是指一个有n个顶点的图，其中每两个点之间都有一条边相连。一个完全二分图是指这样一种图，图中的顶点分为两个点集L和R，L里的每个顶点都和R里的所有点相连。上图显示了一种把K_5划分为四个完全二分图的方法（分别用红蓝绿灰四种颜色来表示这四个子图）。你觉得，最少可以把完全图K_n划分成多少个完全二分图？给出一种划分方案，并证明这个数目已经不能再少了。

和你想象的一样，这个答案就是n-1。一个完全图K_n永远不可能被拆分为n-2个或更少的完全二分图。拆成n-1个是很好办的：从K_n中随便取出一个点作为L集，其余n-1个点作为R集，把这n-1条边从图中取出来形成一个完全二分图，然后继续递归地处理K_(n-1)；当规模降到K_2时，我们已经得到了n-2个二分图，并且图中就只剩下一条边了，合起来正好是n-1个完全二分图。现在的关键是，如何证明n-1个已经是最少的了？
这个证明牛B就牛B在，它根本就不是用组合数学的方法证明的。它居然是用线性代数来证明的！这可以说是我见过的最诡异的证明了。假设我们把K_n划分为了m个完全二分图，第i个二分图的左右两个点集分别记作L_i和R_i。给图中的每个顶点设置一个变量，第i个顶点上的数就记作x_i。于是呢，有

现在，让我们假设m<n-1。考虑下面这个线性方程组：

这个线性方程组的式子个数比未知量少，因此它一定有一组非零解c_1, c_2, ..., c_n。既然每个L_i里面的变量和都为0了，根据前面的那个恒等式，我们得知

考虑所有c_i的和的平方，展开后有

但是，一方面，由线性方程组的第一个方程知c_i的总和为0，其平方当然也等于0；另一方面，c_i是非零解，它的平方和是大于0的。矛盾产生。

题目来源：Proofs from THE BOOK, Chapter 9

UyHiP趣题：(√2 +√3)^1948小数点后第48位是多少？

Matrix67 — Mon, 03 Nov 2008 21:55:16 +0800

作为一个UyHiP的忠实粉丝，我决定把上个月的题目和解答翻译过来，即使类似的把戏我们之前已经见到过了。
题目就一句话：根号2和根号3的和的1948次方的小数点后第48位是多少？如果你立即就想到了正确算法的话，我敢保证在别人还没打开Mathematica的时候你就已经得到答案了。

这道题背后隐藏的把戏就是，(√2 +√3)^1948 + (√2 -√3)^1948永远是一个整数，因为展开之后偶数次幂本来就是整数，而奇数次幂的项恰好又正负互相抵消了。注意到√3 -√2只比0.3多一点，因此(√2 -√3)^1948是一个很小很小的数，粗略估算一下的话它小数点后面紧跟着好几百个“0”；而前面说了(√2 +√3)^1948和(√2 -√3)^1948加起来是个整数，那么前者的小数点后必然有相当长的一段数字9。保守估计的话，不但(√2 +√3)^1948小数点后的第48位是“9”，就是480位也是“9”。事实上，这个数的小数点后面900多位都是“9”。

World of Goo与Sierpinski三角形

Matrix67 — Sun, 02 Nov 2008 21:26:23 +0800

打完了World of Goo，确实是一个难得一见的好游戏。自从打完Portal后，很久没玩到这么好的游戏了。遗憾的是呢，和Portal一样，这个游戏的关卡并不难，游戏时间也太短了一些。一款好的游戏会设置一些在游戏通关后仍然具有可玩性和挑战性的环节，比如这个游戏中你的终极目标就是反复挑战关卡收集尽可能多的球球，在Tower of Goo里面建造尽可能高的塔。如何用尽可能少的球球来建造一个尽可能高的、稳定的塔呢？受到经典分形图形Sierpinski三角形的启发，我打算建这么一个塔（下图为草图），这个样子看上去蛮稳定的（大家认为呢？），并且节省了不少材料。由于球球是可以重新安放的，因此我可以在搭建好三角形后从中间挖出不要的球球来，这给我建造Sierpinski三角形提供了可能性。不过，目前这个工程只做到了2阶，因为我还差球球。大家还想到了什么其它的结构？欢迎在下面和大家分享。