这是一个与扫雷游戏有关的非常好玩的问题。给定一个扫雷布局，定义它的“补集棋盘”为这样一个新布局，原来有雷的地方现在是空地，原来没有雷的地方现在都是雷。在棋盘的每块空地上都标有一个数字，它表示周围的8个方块中有多少颗雷。一个美妙的结论是，两个互补棋盘布局上的数字和是相等的。乍看之下似乎不可思议，但仔细一想便豁然开朗。你能想到这是为什么吗？
图论
随记：普遍性验证、数学思维、代数基本定理及其它
大学生活的乐趣不光体现在吃喝玩乐上，更重要的是它所提供的自由学习的场所。你可以在网上搜索课表，看看什么时候什么教室有什么牛B课，记在手机中的待办事项中，到时候到那个教室去旁听。旁听的乐趣就在于，你可以去学任何你想学的东西，不用交作业，不用怕点你名，不用记笔记，不用考试，只需要挂个耳朵在那儿听牛B东西就行了。前天一大早就被兔子叫起来，跟着一起去旁听了一节数理逻辑。
课程内容很简单，毕竟也才只讲了两周，一切都是很基础的。老师讲得很好，对联结词、命题公式、真值表等概念都说得很细致，即使完全没接触过这方面东西的人也能弄明白。作为信科的专业课，老师也简单提到了SAT问题：给定一串由AND, OR, NOT, 逻辑变量和括号组成的表达式，是否能给变量取值使得整个表达式为真？如果存在这样的“成真赋值”，我们就称表达式是一个“可满足式”。最简单的例子，p∧q就是可满足的，把p、q都取真即可；p∧(¬p)就不可满足，该式无论如何都为假。判断一个逻辑表达式是否可满足是一个经典的NPC问题，目前除了枚举之外还没有更好的算法。
还有一种逻辑表达式，不管初始值是什么，整个式子恒为真。例如，p∨(¬p)就是永真式。看起来，判定一个式子永真比判定一个式子可满足似乎要困难得多，因为前者比后者要强得多。而事实却是，这两个问题可以（在多项式的时间内）相互转化，它们在复杂程度上并无区别。如果你找到了一种可满足式判定算法，你便立即拥有了永真式判定算法。换句话说，你的算法若能找出一个成真赋值，你就能利用该算法立即得出该式所有赋值结果是否都为真。这个问题的问法很有艺术性，它有意屏蔽掉了永假式判定这一桥梁。事实上，一个表达式要么可满足要么永假，而从永假到永真只有一步之遥——只需要在最前面加一个“非”即可。也就是说，如果有一个程序，它能告诉我逻辑表达式A是否可满足，那么我就把¬A输进去：如果它说¬A不可满足，意即¬A的任何赋值结果均为假，反过来A就是永真的；如果它说¬A可以满足，意即程序找到了¬A的一个成真赋值，反过来便成为了A永真的一个反例。
一个难看的证明和一个漂亮的证明
正逢考试周，抱歉这几天更新很慢。最近6天天天都有考试，今天上午考完英语后，终于有机会喘一口气了。下一次考试是后天下午的古代文学史，打算从明天开始借别人的笔记来背。今天下午先稍微休息一下。
前几天准备考离散数学时，烦躁得真想把课本撕了。北大出的那本《离散数学教程》是我所见过的最破的教材，里面频繁出现一些诸如假设m和n怎么怎么样结果推出了p和q怎么怎么样的印刷错误；在短短三页纸中，“Peano”被拼写错了四次，而且每次错的都不一样。
离散数学本身是相当科学的。离散数学中的证明，特别是图论证明，都是相当有趣的。但是，课本上的证明写得太丑了，符号和语言晦涩难懂，思维缺乏直观性和启发性。于是呢，我深刻体会到了这个Blog存在的必要性。我非常反对缺乏直观思维方式的证明过程。一个合格的教科书需要在严格的形式证明之外附上一段证明思路的直观描述。大家或许注意到了，我在写Blog时很不愿意定义变量，能用自然语言描述的地方就尽可能用自然语言来说。在介绍种种精妙的趣题和证明时，我往往会改变证明步骤的顺序和语言表述的方式，以顺应人的直观思维方式；否则，证明的巧妙性和启发性很难被表现出来。
八卦的学问：实现所有人消息共享最少需要多少通电话？
最近看到了一个有趣的问题Gossip Problem。假如我们班有n个MM，每一个MM都有一个独家八卦消息。两个MM可以通过电话联系，一通电话将使得双方都获知到对方目前已知的全部消息。要想所有n个MM都知道所有n条八卦消息，最少需要多少通电话？
一个最简单的办法就是从n个人中选一个消息汇总人，所有n-1个人都打电话给她，她再打电话给所有人。这样总共需要2n-2通电话。其实，汇总阶段的最后一通电话和发布阶段的第一通电话可以合并为一通电话，这样的话该方案实际上只需要2n-3通电话。打电话的次数还能更少吗？给出一个最优解，并证明这个数目已经不能再少了。
显然，n=2时只需要一通电话，n=3时必须要3通电话。当n=4时，可以让AB互相通话，CD互相通话，此时每个人都知道了（包括自己的）两条消息；然后A和C通话，B和D通话，从而使得每个人都获知另外两条自己还不知道的消息。显然，对于4个人的情况，4通电话已经是最少的了。
对于n>4的情况，有一种算法可以保证在2n-4通电话内解决问题。首先，选出4个人作为消息汇总人。其余每个人都选择一个汇总人并与之通话；然后4个汇总人再用4通电话互相更新一下消息（用刚才n=4的办法）；最后4个汇总人把电话再打回去，实现所有消息全部共享。下面我们证明，2n-4已经是最少的了。证明方法很多，也都很复杂。最常见的证明由Brenda Baker和Robert Shostak在1972年给出。
经典证明：不用数学归纳法直接推导平面图的Euler公式
把《三体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。