Matrix67 |
2010-05-19 22:30 | 
23. 一些硬币互不重叠地放在桌上。四色定理告诉我们，若要对硬币进行染色，使得挨在一起的硬币颜色不同的话，最多只需要四种颜色就可以了。存在至少需要四种颜色的构造吗？
答案：存在。如图，若只允许三种颜色的话， A 的颜色必须与所有阴影硬币颜色相同， B 的颜色也必须与所有阴影硬币颜色相同， A 、 B 将会同色。
May
19
Mar
19
引言 什么是算法
如何寻找稳定的婚姻搭配
据说，一本书开篇就直言不讳地谈起两性的话题，这本书准能畅销。有幸的是，在众多可以用来引入“算法”的话题中，我最喜欢的那一个还真与两性有那么一些关系。假如你是一个媒人，有若干个单身男子登门求助，还有同样多的单身女子也前来征婚。如果你已经知道这些女孩在每个男人心目中的排名，以及男孩们在每个女孩心中的排名(1)，你应该怎样为他们牵线配对呢？
最好的配对方案当然是，每个人的另一半正好都是自己的“第一选择”。这虽然很完美，但绝大多数情况下都不可能实现。比方说，男 1 号的最爱是女 1 号，而女 1 号的最爱不是男 1 号，这两个人的最佳选择就不可能被同时满足。如果出现了好几个男人的最爱都是同一个女孩儿的情况，这几个男人的首选也不会同时得到满足。当这种最为理想的配对方案无法实现时，怎样的配对方案才能令人满意呢？
其实，找的对象太完美不见得是个好事儿，和谐才是婚姻的关键。如果男 1 号和女 1 号各自有各自的对象，但男 1 号觉得，比起自己现在的对象，女 1 号更好一些；女 1 号也发现，在自己心目中，男 1 号的排名比现男友更靠前一些。这样一来，这两人就可能会发生外遇，最后扔下各自现在的对象，一起私奔了——因为这个结果对他们两人都更好一些。在一种男女配对的方案中，如果出现了这种情况，我们就说婚姻搭配是不稳定的。作为一个红娘，你深深地知道，对象介绍得不好没有关系，就怕婚姻关系不稳定。给客户牵线配对时，虽然不能让每个人都得到最合适的，但婚姻搭配必须得是稳定的。换句话说，对于每一个人，在他心目中比他当前的伴侣更好的异性，都不会认为他也是一个更好的选择。现在，我们的问题就是：稳定的婚姻搭配总是存在吗？应该怎样寻找出一个稳定的婚姻搭配？
Sep
17
在各种介绍密码学与协议的教材里都有关于零知识证明的话题——如何让你相信我已经找到了一个解，但又不告诉你这个解是什么。最经典的例子便是关于Hamilton回路的问题——存在这样一种巧妙的协议，可以让你相信我已经找到了某个图的Hamilton回路，而你却完全得不到关于这个Hamilton回路本身的任何信息。今天我又看到了一个非常不错的零知识证明实例。给定一个平面图，你需要给每个区域染一种颜色，使得任两个相邻的区域颜色不同。如果你仅用三种颜色就能做到这一点，我们就说这个图是可以三染色的。目前我们还没有一个判断平面图可否三染色的好办法，寻找一个平面图的三染色方案并不是一件容易的事。现在，假如你已经找到了某个给定平面图的三染色方案，你想向别人炫耀自己的成果，但又不想透露关于你的染色方案的任何信息。你能否设计一种协议使得对方能够相信你确实找到了一种三染色方案而又不告诉他这种方案是什么呢？
Jul
20
假设我们俩各自独立地随机选取一个有无穷多个顶点的图（两点之间1/2的概率有边1/2的概率没有边）。那么，我们俩选到相同的图的概率是多少？
令人难以置信、但想通了之后又异常显然的是，两个图相同的概率为1。并且，我可以精确地告诉你，这个相同的图是什么样子的。考虑这样一个无穷大的图，我们用自然数1, 2, 3, ...给所有顶点标号，然后如果y的二进制表达中的右起第x位为1，就在顶点x和顶点y之间连一条线。比如，顶点5就和顶点1、顶点3相连。我可以证明，我们俩都100%地会选取到上述这个图。
May
10
昨天和老朋友BY一起吃饭时又一次不可避免地谈到了算法问题。一个有趣的话题是：提起那些最巧妙的、最离奇的牛B算法时，你想到的第一个算法题是什么？
我第一想到的算法题是那道经典问题：n个数中有且仅有一个数出现了奇数次（其它数都出现了偶数次），如何用线性时间常数空间找出这个数。解法也只有一句话：从头到尾异或一遍，结果就是要求的那个数。该问题的加强版也异常牛B，我曾经在这里介绍过。不过，这个算法我在茶余饭后已经聊过无数次了……
脑海中出现的另一个牛B算法题则是POJ3318：给你三个n*n的矩阵A、B、C，问你A*B是不是等于C。数据保证O(n^3)铁定超时，因此你需要想一个不用把A和B乘起来就可以验证的算法。一个基于概率的算法是随机生成一个n乘1的矩阵R，然后判断A*B*R是否等于C*R，而前者相当于A*(B*R)，与后者一样都可以在O(n^2)的时间里算出来。如果算出来的结果相等，几乎可以肯定A*B和C也是相等的。
May
6
我们上次说到，不是所有的平面图都是可4选择的。于是人们接着猜想，是不是所有平面图都是可5选择的呢？1994年，Carsten Thomassen证明了，所有平面图都是可5选择的。这个证明极其简单，论文全文不足两页，证明过程仅十多行。证明对平面图中的区域数n施归纳。有趣的是，归纳的命题比我们待证明的命题要强得多，否则原命题反而证不到。
为简便起见，我们假设平面图是一般的，它没有同属于四块区域的交界点，也没有中空的“洞”。加入这些条件不会让问题变得更简单，因此这些假设都是合理的。下面再假设最外面那一圈区域（与“外部空间”相邻的区域）有s个，它们彼此相连构成了一个环，我们按逆时针顺序把它们分别记为P_1, P_2, P_3, ..., P_s。无妨设P_1和P_2的颜色分别为1和2。下面我们证明一个比原命题更强的结论：若最外面那s个区域的颜色列表中至少有三个颜色，其余那些（被围在内部的）区域的颜色列表中有五个颜色，则一定存在合法的列表染色。当区域数n足够小时结论显然成立。
Apr
27
四色定理告诉我们，给地图上的每个区域涂一种颜色，为了使相邻的区域有不同的颜色，我们总共只需要4种颜色就够了。不过，万一有些省装怪，偏不喜欢分配给它的颜色该咋办？这下问题就变得有意思起来了。为了满足不同省市的要求，国家测绘局可以在为地图染色前先让每个省市列出自己能够接受的几种颜色，染色时就只从每个省市给出的候选颜色中取色。我们把每一个使得相邻区域的颜色互不相同的染色方案叫做一种列表染色(list coloring)。现在的问题是，至少要求每个省市列出多少个候选颜色才能使合法的列表染色总是存在，不管这些颜色列表是什么？如果每个省市列出k种颜色就足够了，我们就称该地图是可k选择的(k-choosable)。或许大家会想，k=4就够了吧，毕竟四色定理保证了只使用4种颜色一定能实现合法的染色，而在列表染色问题里总的颜色很可能还不止4种，同时相邻区域的公共颜色数量也将减少。但是，数学家们早就注意到，能够k着色的平面图不见得就一定可以k选择。例如，下面这个图显然可以二着色，但它就不是二选择的——如果每个区域的颜色列表如图中所示，则不存在满足要求的列表染色。因此，人们普遍认为，并不是每个平面图都是可4选择的。
不过，数学家们一直没能找到不可4选择的平面图。1993年，Voigt发现了第一个不能4选择的平面图，它有238块区域。构造方法非常具有启发性，从里面能看到不少数学思维方法。
Apr
16
（拜托转载时请用红色加粗字体标明，这是我古今数学思想课的期中论文，免得老师以为我是反过来抄的网上的文章。这门通选课的期中论文要求写数学与自己所在专业之间的联系。）
我们每天都在说话，每天都在用语言进行交流。语言文字对我们是如此的平常，以至于绝大多数人都不会注意到语言中一些非常难以解释的现象。昨天的汉语虚词研究课上，我们就谈到了这样一个有趣的问题：在表示“仅仅”的含义时，什么时候能够用“只”，什么时候能够用“光”？若不细想的话，大家或许会认为两者的用法完全一样。“我只吃苹果”可以说成“我光吃苹果”，“光有知识还不行”也可以说成是“只有知识还不行”。我们还可以举出更多的例子来，如“别光坐着”/“别只坐着”，“光说不做”/“只说不做”等等。凭借天生的归纳性思维，一个正常人有充分的理由猜想，在表示“仅仅”的含义时，“只”和“光”是通用的。而事实上，现代汉语词典中正是把“光”字解释为“只”。有趣的是，在我们质疑只找了四个例子是否足以说明二者等价时，殊不知这句质疑本身就成了一个反例：“只找了四个例子”不能换成“光找了四个例子”。类似地，“大会只来了748个人”也不能说“大会光来了748个人”。我们继续猜想，是不是“光”不能用在数量词前面呢？也不见得。当数量词不是实指而是虚指时，我们有时也能用“光”来修饰带有数量词的名词。例如，在表示“只吃几个苹果”、“只吃一些苹果”的意义时，“光吃两个苹果”的说法是很顺口的。另一些例子则表明，“光”的用法似乎与它所修饰的名词无关。“我只当到团长”不能说成是“我光当到团长”，但怪就怪在“我只认识团长”却又偏偏可以说成是“我光认识团长”。“当到团长”和“认识团长”有什么不同呢？仔细揣摩两者的意思，我们似乎体会到了一些微妙的差别：“当到团长”是一个阶段性的、进度性的、里程碑性的概念，它必须事先经过“当到连长”、“当到营长”等事件；但“认识团长”就不一样了，没有任何规定限制我们在“认识团长”之前必须“认识连长”。同样的，“找出四个例子”是以“找了三个例子”为前提的，“来了748个人”也不是一下子就能实现的。
问题算是想通了，但怎么来阐述它呢？在这个问题上，语言学陷入了一个困境。此时，引入数理逻辑语言对于解释这种语言现象出乎意料的方便。我们说，在副词“只”修饰的事件所处的“域”中如果存在蕴含关系，则这里的“只”不能用“光”来替代。例如，提起“吃两个苹果”，我们脑海中形成的事件集合一定是“吃一个苹果”、“吃两个苹果”、“吃三个苹果”等等，而后者必然蕴含前者，因此“只吃两个苹果”不能说成“光吃两个苹果”。类似的，“当到团长”必然推出“当到连长”，但有“认识团长”不见得有“认识连长”，因此两者与“只”和“光”的搭配情况是不同的。
