四色定理告诉我们，给地图上的每个区域涂一种颜色，为了使相邻的区域有不同的颜色，我们总共只需要4种颜色就够了。不过，万一有些省装怪，偏不喜欢分配给它的颜色该咋办？这下问题就变得有意思起来了。为了满足不同省市的要求，国家测绘局可以在为地图染色前先让每个省市列出自己能够接受的几种颜色，染色时就只从每个省市给出的候选颜色中取色。我们把每一个使得相邻区域的颜色互不相同的染色方案叫做一种列表染色(list coloring)。现在的问题是，至少要求每个省市列出多少个候选颜色才能使合法的列表染色总是存在，不管这些颜色列表是什么？如果每个省市列出k种颜色就足够了，我们就称该地图是可k选择的(k-choosable)。或许大家会想，k=4就够了吧，毕竟四色定理保证了只使用4种颜色一定能实现合法的染色，而在列表染色问题里总的颜色很可能还不止4种，同时相邻区域的公共颜色数量也将减少。但是，数学家们早就注意到，能够k着色的平面图不见得就一定可以k选择。例如，下面这个图显然可以二着色，但它就不是二选择的——如果每个区域的颜色列表如图中所示，则不存在满足要求的列表染色。因此，人们普遍认为，并不是每个平面图都是可4选择的。

    不过，数学家们一直没能找到不可4选择的平面图。1993年，Voigt发现了第一个不能4选择的平面图，它有238块区域。构造方法非常具有启发性，从里面能看到不少数学思维方法。

查看更多 »

    小时候我就很喜欢思考一些科学之外的东西。数学家发现新定理，物理学家提出新理论，发明家创造新事物，自以为无所不能的科学似乎已经统领了整个人类历史的发展。但是，谁又来思考科学本身呢？于是我常常幻想，如果当初科学没有战胜宗教，世界又将怎样？人类依旧停留在穷困的黑暗社会？还是与大自然和睦相处过着无忧无虑的幸福生活？甚至是凭借直觉和信仰建立了一套能够自圆其说的物理体系，虽然这套体系和我们现有理论大相径庭？无论怎样，如果我们当真生活在宗教胜出的那个平行世界中，我们不但不会质疑这个问题，相反还会问自己如果科学战胜了宗教的话生活会变得多么不可思议。因为“科学”的定义变了。
    我们到底应该如何获取知识，如何探索世界，在这个根本问题上的分歧形成了不同的“科学范式”。一个科学范式下理所当然的东西在另一个科学范式下可能变得无比荒谬，因为它们在科学发展的最底层就已经有了矛盾。当宗教统治人类历史时，宗教便是“科学”；外人看来再不合理的事情，只要是在自己圈子里发展出来的，怎么看都再正常不过。宗教与科学之争其实是两个科学范式之间的战争，它们的争端永远没有办法解决，因为各自的理论在各自的研究方法之下都是正确的，它们本身并无对错之分，谁也说服不了谁。我们或许期待着有那么一套“算法”作为法官来评判哪个科学范式更好，不幸的是这个法官本身所代表的就是第三种科学范式，争端不但没有任何缓和，反而扩大了。
    前几天刚看完《科学哲学》这本书。科学哲学很有意思。这里我举一个有趣例子来说明，科学哲学问题相当值得思考。

查看更多 »

正在上虚词研究课，好友Chain发来短信说，北大BBS化学学院版上发了一道很有趣的谜题，已经上十大热门话题第三了。我也是第一次看到这个题目，和大家分享一下。

话说周一某实验室有16名同学，有一天*老师把大家叫到一起说：下周来做实验的时候，我会给你们每个人背后贴一张纸，纸上的数字从1到16都有可能，不同同学背后的数字可以重复。你们每个人可以看到别人背上的数字，但不能看到自己的数字。贴纸之后你们之间不允许进行任何形式的沟通交流。之后你们排队依次来D***，告诉我你自己背后的数字是多少；由于D***室隔音效果很好，室外的人不能听到室内的同学的说话声（更好的说法是，每个人独自在一张小纸条上写下猜测结果，这就避免了可能由排队猜数的时间和顺序带来的“交流”）。等到16名同学都猜完之后公布结果。只要你们16个人中间能有一个人猜对自己背后的数字，我会让大家都得满分；但如果你们都没有猜对自己背后的数字的话，则你们全部都要重修有机实验。那么你要怎样做才能避免挂科的命运呢？

这道题目很有意思，看答案之前不妨自己先想一下。
提示：先从两个人的情况开始想起。

查看更多 »

昨天我突发奇想，写了几段Mathematica代码，生成了各种排序算法的内存变化图。图中每一个新的横行都表示数组的一次更新，数字大小用颜色来表示。你可以直观地看到这些算法是如何把乱序数组一点一点变为有序的。效果还是很令人满意的，不少算法的内存轨迹都相当美观，相当有艺术性。

图很大，我就不在首页上显示了，大家点“查看更多”看图吧。

查看更多 »

来自friendlyatheist.com的一个邪恶的笑话，它告诉我们，在讲课之前先自己排演一遍有多么重要。

老师：同学们，这是一个什么形状啊？

学生：（齐声）四棱锥！

查看更多 »

    网友Qian Yongchao发来邮件说，他在阅读当前正大红大紫的一本书叫做Outliers。书中谈到IQ测试时，作者提到了Raven's Progressive Matrices测试法。这是一系列从易到难的题目，一般有48道题。为了说明这种测试可以有多难，作者给出了整个测试的最后一道题，这道题目即使作者自己也不知道该怎么做。我在网上搜索了一下，确信书上印的题目是错误的。其实，那道题就是iqtest.dk上的那个火星IQ测试的最后一题。这个题确实很难，无数人都卡在这上面死活想不明白。

查看更多 »

    我们知道，存在这样一种全体正整数的红蓝二着色方案，其中没有任何无穷长的等差数列满足数列中的所有数颜色都一样。它的构造非常暴力。有趣的是，把上述命题中的“无穷长”换成“任意长”，命题就不见得仍然正确了。事实上，Van der Waerden定理告诉我们，对于任意大的k，总存在一个N，使得对从1到N的正整数进行红蓝二染色后，里面总存在一个单色的长为k的等差数列。当命题扩展到任意c着色时，该命题竟然也都成立。证明主要用了鸽笼原理和数学归纳法，证明过程直观而又有趣。

    我们首先来证明k=3的情况：存在某个N使得对N个连续自然数进行二染色后里面总有长为3的单色等差数列。我们把全体正整数5个5个地分组，1..5为第一组，6..10为第二组，以此类推。每一组里总共有2^5种不同的染色方案，因此在前2^5+1组里面必然有两个组的染色一模一样，比方说第7组和第23组吧。把第7组里的数记作A_1, A_2, ..., A_5，由鸽笼原理，A_1, A_2, A_3里面一定存在两个颜色相同的数，不妨设A_1和A_3都是红色吧。考虑A_5的颜色：如果它是红色，我们的问题就解决了，A_1, A_3, A_5已经是一个长度为3的等差数列。下面考虑A_5是蓝色的情况。别忘了第7组和第23组的染色完全相同，因此在第23组中，B_1, B_3也是红色，B_5也是蓝色。下面我们来考虑全体正整数的第39组（7,23,39是等差数列），我们把它记为C_1, C_2, ..., C_5。考虑C_5的颜色：如果它是红色，那A_1, B_3, C_5就是一个全为红色的等差数列，否则A_5, B_5, C_5就是一个全为蓝色的等差数列。显然，上述证明中的“最坏情况”就是，第1组和第33组的染色相同，且第1组的第1个数和第33组的第3个数是红色，则下一个数最远可以是第65组的第5个数，即全体正整数的第325个数。换句话说，k=3时N=325即满足条件。

查看更多 »

（拜托转载时请用红色加粗字体标明，这是我古今数学思想课的期中论文，免得老师以为我是反过来抄的网上的文章。这门通选课的期中论文要求写数学与自己所在专业之间的联系。）

    我们每天都在说话，每天都在用语言进行交流。语言文字对我们是如此的平常，以至于绝大多数人都不会注意到语言中一些非常难以解释的现象。昨天的汉语虚词研究课上，我们就谈到了这样一个有趣的问题：在表示“仅仅”的含义时，什么时候能够用“只”，什么时候能够用“光”？若不细想的话，大家或许会认为两者的用法完全一样。“我只吃苹果”可以说成“我光吃苹果”，“光有知识还不行”也可以说成是“只有知识还不行”。我们还可以举出更多的例子来，如“别光坐着”/“别只坐着”，“光说不做”/“只说不做”等等。凭借天生的归纳性思维，一个正常人有充分的理由猜想，在表示“仅仅”的含义时，“只”和“光”是通用的。而事实上，现代汉语词典中正是把“光”字解释为“只”。有趣的是，在我们质疑只找了四个例子是否足以说明二者等价时，殊不知这句质疑本身就成了一个反例：“只找了四个例子”不能换成“光找了四个例子”。类似地，“大会只来了748个人”也不能说“大会光来了748个人”。我们继续猜想，是不是“光”不能用在数量词前面呢？也不见得。当数量词不是实指而是虚指时，我们有时也能用“光”来修饰带有数量词的名词。例如，在表示“只吃几个苹果”、“只吃一些苹果”的意义时，“光吃两个苹果”的说法是很顺口的。另一些例子则表明，“光”的用法似乎与它所修饰的名词无关。“我只当到团长”不能说成是“我光当到团长”，但怪就怪在“我只认识团长”却又偏偏可以说成是“我光认识团长”。“当到团长”和“认识团长”有什么不同呢？仔细揣摩两者的意思，我们似乎体会到了一些微妙的差别：“当到团长”是一个阶段性的、进度性的、里程碑性的概念，它必须事先经过“当到连长”、“当到营长”等事件；但“认识团长”就不一样了，没有任何规定限制我们在“认识团长”之前必须“认识连长”。同样的，“找出四个例子”是以“找了三个例子”为前提的，“来了748个人”也不是一下子就能实现的。

    问题算是想通了，但怎么来阐述它呢？在这个问题上，语言学陷入了一个困境。此时，引入数理逻辑语言对于解释这种语言现象出乎意料的方便。我们说，在副词“只”修饰的事件所处的“域”中如果存在蕴含关系，则这里的“只”不能用“光”来替代。例如，提起“吃两个苹果”，我们脑海中形成的事件集合一定是“吃一个苹果”、“吃两个苹果”、“吃三个苹果”等等，而后者必然蕴含前者，因此“只吃两个苹果”不能说成“光吃两个苹果”。类似的，“当到团长”必然推出“当到连长”，但有“认识团长”不见得有“认识连长”，因此两者与“只”和“光”的搭配情况是不同的。

查看更多 »