昨天和老朋友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也是相等的。
我们上次说到，不是所有的平面图都是可4选择的。于是人们接着猜想，是不是所有平面图都是可5选择的呢？1994年，Carsten Thomassen证明了，所有平面图都是可5选择的。这个证明极其简单，论文全文不足两页，证明过程仅十多行。证明对平面图中的区域数n施归纳。有趣的是，归纳的命题比我们待证明的命题要强得多，否则原命题反而证不到。
为简便起见，我们假设平面图是一般的，它没有同属于四块区域的交界点，也没有中空的“洞”。加入这些条件不会让问题变得更简单，因此这些假设都是合理的。下面再假设最外面那一圈区域（与“外部空间”相邻的区域）有s个，它们彼此相连构成了一个环，我们按逆时针顺序把它们分别记为P_1, P_2, P_3, …, P_s。无妨设P_1和P_2的颜色分别为1和2。下面我们证明一个比原命题更强的结论：若最外面那s个区域的颜色列表中至少有三个颜色，其余那些（被围在内部的）区域的颜色列表中有五个颜色，则一定存在合法的列表染色。当区域数n足够小时结论显然成立。
四色定理告诉我们，给地图上的每个区域涂一种颜色，为了使相邻的区域有不同的颜色，我们总共只需要4种颜色就够了。不过，万一有些省装怪，偏不喜欢分配给它的颜色该咋办？这下问题就变得有意思起来了。为了满足不同省市的要求，国家测绘局可以在为地图染色前先让每个省市列出自己能够接受的几种颜色，染色时就只从每个省市给出的候选颜色中取色。我们把每一个使得相邻区域的颜色互不相同的染色方案叫做一种列表染色(list coloring)。现在的问题是，至少要求每个省市列出多少个候选颜色才能使合法的列表染色总是存在，不管这些颜色列表是什么？如果每个省市列出k种颜色就足够了，我们就称该地图是可k选择的(k-choosable)。或许大家会想，k=4就够了吧，毕竟四色定理保证了只使用4种颜色一定能实现合法的染色，而在列表染色问题里总的颜色很可能还不止4种，同时相邻区域的公共颜色数量也将减少。但是，数学家们早就注意到，能够k着色的平面图不见得就一定可以k选择。例如，下面这个图显然可以二着色，但它就不是二选择的——如果每个区域的颜色列表如图中所示，则不存在满足要求的列表染色。因此，人们普遍认为，并不是每个平面图都是可4选择的。
不过，数学家们一直没能找到不可4选择的平面图。1993年，Voigt发现了第一个不能4选择的平面图，它有238块区域。构造方法非常具有启发性，从里面能看到不少数学思维方法。
（拜托转载时请用红色加粗字体标明，这是我古今数学思想课的期中论文，免得老师以为我是反过来抄的网上的文章。这门通选课的期中论文要求写数学与自己所在专业之间的联系。）
我们每天都在说话，每天都在用语言进行交流。语言文字对我们是如此的平常，以至于绝大多数人都不会注意到语言中一些非常难以解释的现象。昨天的汉语虚词研究课上，我们就谈到了这样一个有趣的问题：在表示“仅仅”的含义时，什么时候能够用“只”，什么时候能够用“光”？若不细想的话，大家或许会认为两者的用法完全一样。“我只吃苹果”可以说成“我光吃苹果”，“光有知识还不行”也可以说成是“只有知识还不行”。我们还可以举出更多的例子来，如“别光坐着”/“别只坐着”，“光说不做”/“只说不做”等等。凭借天生的归纳性思维，一个正常人有充分的理由猜想，在表示“仅仅”的含义时，“只”和“光”是通用的。而事实上，现代汉语词典中正是把“光”字解释为“只”。有趣的是，在我们质疑只找了四个例子是否足以说明二者等价时，殊不知这句质疑本身就成了一个反例：“只找了四个例子”不能换成“光找了四个例子”。类似地，“大会只来了748个人”也不能说“大会光来了748个人”。我们继续猜想，是不是“光”不能用在数量词前面呢？也不见得。当数量词不是实指而是虚指时，我们有时也能用“光”来修饰带有数量词的名词。例如，在表示“只吃几个苹果”、“只吃一些苹果”的意义时，“光吃两个苹果”的说法是很顺口的。另一些例子则表明，“光”的用法似乎与它所修饰的名词无关。“我只当到团长”不能说成是“我光当到团长”，但怪就怪在“我只认识团长”却又偏偏可以说成是“我光认识团长”。“当到团长”和“认识团长”有什么不同呢？仔细揣摩两者的意思，我们似乎体会到了一些微妙的差别：“当到团长”是一个阶段性的、进度性的、里程碑性的概念，它必须事先经过“当到连长”、“当到营长”等事件；但“认识团长”就不一样了，没有任何规定限制我们在“认识团长”之前必须“认识连长”。同样的，“找出四个例子”是以“找了三个例子”为前提的，“来了748个人”也不是一下子就能实现的。
问题算是想通了，但怎么来阐述它呢？在这个问题上，语言学陷入了一个困境。此时，引入数理逻辑语言对于解释这种语言现象出乎意料的方便。我们说，在副词“只”修饰的事件所处的“域”中如果存在蕴含关系，则这里的“只”不能用“光”来替代。例如，提起“吃两个苹果”，我们脑海中形成的事件集合一定是“吃一个苹果”、“吃两个苹果”、“吃三个苹果”等等，而后者必然蕴含前者，因此“只吃两个苹果”不能说成“光吃两个苹果”。类似的，“当到团长”必然推出“当到连长”，但有“认识团长”不见得有“认识连长”，因此两者与“只”和“光”的搭配情况是不同的。
概率论并不仅仅是用来算算概率的。有些时候，概率论远比我们想象中的更强大。
考虑这样一个问题。考虑集合X上的一个集合族，集合族中的所有集合大小均为d。我们说这个集合族是可以二染色的，如果对X的元素进行适当的红蓝二着色之后，每个集合里面都包含了两种颜色的元素。例如，当d=3时，{1,2,3}, {1,2,4}, {1,3,4}, {2,3,5}就是可二染色的，把1、2染成红色，把3、4、5染成蓝色，则每个集合里都含有两种颜色。是否存在d=3的不可二染色集族呢？这样的集族当然是存在的，例如取集合{1,2,3,4,5}的全部C(5,3)个元素个数为3的子集，则无论如何染色，总会有一个集合里面的元素全是一种颜色。上述推理立即告诉我们，对于一个给定的d，一定存在一个集合个数为C(2d-1, d)的不可二染色集族。这个数目还能再少吗？我们想知道，不可二染色集族中的集合个数最少可以少到什么地步。一个极其简单的证明给出了一个下界：集族的大小一定大于2^(d-1)。当d=3时，你一辈子也不能构造一个不可二染色集族，里面只含4个集合。
为了证明这一点，不妨对X中的所有元素进行随机着色，每个元素取成红色和蓝色的概率均等。那么，一个元素个数为d的集合中，所有元素均为一种颜色的概率就应该是1/2^(d-1)。如果集族内的集合个数只有不到2^(d-1)个，那么即使“集合中是否只有一种颜色”是互相独立的，这些事件的并（至少有一个集合内只有一种颜色）的概率也不超过2^(d-1) * 1/2^(d-1) = 1，何况这些事件还不是独立的，因此存在单色集合的概率必然小于1。这个概率值小于1说明什么？这说明，“至少有一个单色集合”并不是必然事件，一定有一种染色方案使得每个元素里都含两种颜色，换句话说该集族可以被二染色。