今天是我第一次听说这个故事。
1933 年，匈牙利数学家 George Szekeres 还只有 22 岁。那时，他常常和朋友们在匈牙利的首都布达佩斯讨论数学。这群人里面还有同样生于匈牙利的数学怪才——Paul Erdős 大神。不过当时，Erdős 只有 20 岁。
在一次数学聚会上，一位叫做 Esther Klein 的美女同学提出了这么一个结论：在平面上随便画五个点（其中任意三点不共线），那么一定有四个点，它们构成一个凸四边形。Szekeres 和 Erdős 等人想了好一会儿，没想到该怎么证明。于是，美女同学得意地宣布了她的证明：这五个点的凸包（覆盖整个点集的最小凸多边形）只可能是五边形、四边形和三角形。前两种情况都已经不用再讨论了，而对于第三种情况，把三角形内的两个点连成一条直线，则三角形的三个顶点中一定有两个顶点在这条直线的同一侧，这四个点便构成了一个凸四边形。
Johann Carl Friedrich Gauss（1777－1855），史上最牛的数学家。他上知天文，下知地理，涉足数学各个领域，死后都在用未知的神秘力量影响着数学的发展。作为当之无愧的第一大数学家，Gauss 有很多鲜为人知的传奇经历，现在就为你一一八卦：
来源：http://www.gaussfacts.com （太欢乐了）
记得第一次了解中文分词算法是在 Google 黑板报 上看到的，当初看到那个算法时我彻底被震撼住了，想不到一个看似不可能完成的任务竟然有如此神奇巧妙的算法。最近在詹卫东老师的《中文信息处理导论》课上再次学到中文分词算法，才知道这并不是中文分词算法研究的全部，前前后后还有很多故事可讲。在没有建立统计语言模型时，人们还在语言学的角度对自动分词进行研究，期间诞生了很多有意思的理论。
中文分词的主要困难在于分词歧义。“结婚的和尚未结婚的”，应该分成“结婚／的／和／尚未／结婚／的”，还是“结婚／的／和尚／未／结婚／的”？人来判断很容易，要交给计算机来处理就麻烦了。问题的关键就是，“和尚未”里的“和尚”也是一个词，“尚未”也是一个词，从计算机的角度看上去，两者似乎都有可能。对于计算机来说，这样的分词困境就叫做“交集型歧义”。
有时候，交集型歧义的“歧义链”有可能会更长。“中外科学名著”里，“中外”、“外科”、“科学”、“学名”、“名著”全是词，光从词库的角度来看，随便切几刀下去，得出的切分都是合理的。类似的例子数不胜数，“提高产品质量”、“鞭炮声响彻夜空”、“努力学习语法规则”等句子都有这样的现象。在这些极端例子下，分词算法谁优谁劣可谓是一试便知。
前几天，一篇叫做 用正方形纸片折出等边三角形 的日志引起大家的讨论，折出正七边形和折出角三等分线的方案更是让大家争论不休。提得最多的问题就是，折纸为什么要比尺规作图更强？这是一个好问题。我查了不少资料，了解到不少折纸几何的历史，收获颇大，不赶紧记下来就亏大了。于是有了这篇文章。
要解答为何折纸如此强大，首先我们得解决一个问题：什么叫折纸。折纸的游戏规则是什么？换句话说，折纸允许哪些基本的操作？大家或许会想到一些折纸几何必须遵守的规则：所有直线都由折痕或者纸张边缘确定，所有点都由直线的交点确定，折痕一律是将纸张折叠压平再展开后得到的，每次折叠都要求对齐某些已有几何元素（不能凭感觉乱折），等等。不过，这些定义都太“空”了，我们需要更加形式化的折纸规则。 1991 年， Humiaki Huzita 指出了折纸过程中的 6 种基本操作（也可以叫做折纸几何的公理）：
1. 已知 A 、 B 两点，可以折出一条经过 A 、 B 的折痕
在准备前一篇日志时，我查阅了很多经典的悖论。我发现，虽说数学悖论大多是一些让人越想越糊涂的逻辑思维游戏，但也有不少悖论来自于实实在在的数学问题。在缺乏现代数学工具的年代，这些反直觉的结论和看似不可调和的矛盾让数学家们百思不得其解，那些最难解决的悖论甚至为数学新分支的开创带来了足够的动机。不太为人熟知的 Cramer 悖论就是一个漂亮的例子。
在描述 Cramer 悖论之前，让我们先来考虑一个简单的情况。两条直线交于一点。反过来，过一点可以做两条不同的直线。事实上，过一点可以做无数条直线。确定一条直线需要两个点才够。一切都很正常。
现在，考虑平面上的两条三次曲线。由于将两个二元三次方程联立求解，最多可以得到 9 组不同的解，因此两条三次曲线最多有 9 个交点。另外，三次曲线的一般形式为
x^3 + a·x^2·y + b·x·y^2 + c·y^3 + d·x^2 + e·x·y + f·y^2 + g·x + h·y + i = 0
这里面一共有 9 个未知系数。代入曲线上的 9 组不同的 (x, y) ，我们就能得出 9 个方程，解出这 9 个未知系数，恢复出这个三次曲线的原貌。也就是说，平面上的 9 个点唯一地确定了一个三次曲线。这次貌似就出问题了： “两条三次曲线交于 9 个点” 和 “ 9 个点唯一地确定一条三次曲线” 怎么可能同时成立呢？既然这 9 个点是两条三次曲线所共有的，那它们究竟会“唯一地”确定出哪条曲线呢？在没有线性代数的年代，这是一个令人匪夷所思的问题。
我一直觉得，数学中的各种常数是最令人敬畏的东西，它们似乎是宇宙诞生之初上帝就已经精心选择好了的。那一串无限不循环的数字往往会让人陷入一种无底洞般的沉思——为什么这串数字就不是别的，偏偏就是这个样呢。除了那些众所周知的基本常数之外，还有很多非主流的数学常数，它们的存在性和无理性同样给它们赋予了浓重的神秘色彩。今天，就让我们一起来看一看，数学当中到底有哪些神秘的无理常数。
√2 ≈ 1.4142135623730950488
古希腊的大哲学家 Pythagoras 很早就注意到了数学与大千世界的联系，对数学科学的发展有着功不可没的贡献。他还创立了在古希腊影响最深远的学派之一—— Pythagoras 学派。 Pythagoras 学派对数字的认识达到了审美的高度。他们相信，在这个世界中“万物皆数”，所有事物都可以用整数或者整数之比来描述。
第一个无理数 √2 的发现者就是一位 Pythagoras 学派的学者，他叫做 Hippasus 。据说，一日 Hippasus 向 Pythagoras 提出了这样的问题：边长为 1 的正方形，对角线长度能用整数之比来表示吗？ Pythagoras 自己做了一些思考，证明了这个数确实无法用整数之比来表示。由于这一发现触犯了学派的信条，因此 Pythagoras 杀害了 Hippasus 。
利用勾股定理可知，这个数是方程 x^2 = 2 的唯一正数解，我们通常就记作 √2 。 √2 可能是最具代表性的无理数了，我们之前曾经介绍过很多 √2 的无理性的证明。无理数的出现推翻了古希腊数学体系中的一个最基本的假设，直接导致了第一次数学危机，整座数学大厦险些轰然倒塌。
无理数虽说无理，在生产生活中的用途却是相当广泛。例如，量一量你手边的书本杂志的长与宽，你会发现它们的比值就约为 1.414 。这是因为通常印刷用的纸张都满足这么一个性质：把两条宽边对折到一起，得到一个新的长方形，则新长方形的长宽之比和原来一样。因此，如果原来的长宽比为 x : 1 ，新的长宽比就是 1 : x/2 。解方程 x : 1 = 1 : x/2 就能得到 x = √2 。
说有 100 个囚犯分别关在 100 间牢房里。牢房外有一个空荡荡的房间，房间里有一个由开关控制的灯泡。初始时，灯是关着的。看守每次随便选择一名囚犯进入房间，但保证每个囚犯都会被选中无穷多次。如果在某一时刻，有囚犯成功断定出所有人都进过这个房间了，所有囚犯都能释放。游戏开始前，所有囚犯可以聚在一起商量对策，但在此之后它们唯一可用来交流的工具就只有那个灯泡。他们应该设计一个怎样的协议呢？
这个经典的问题在网上转载无数，题目描述被好事者们改得天花乱坠，甚至加进了“这盏灯永远有充足的能源供应”、“如果灯泡坏了或是电路出了故障会马上修好”等条件，剥掉了“算法问题”的外壳，填补了本不存在的漏洞，让更多的人动起了脑筋。在论坛上，每次贴出这个问题，总会引起一大群人的口水战。但很不幸的是，这个题目的来源至今仍是个谜。据目前的已知情况推测，这个题目最早来源于 Berkeley 的电气工程荣誉学会，时间大概是 2001 年。在 2002 年的 7 月， IBM 的 Ponder This 趣题栏目介绍这个题目，囚犯与灯泡一炮走红，随即遍布网络的各个角落。 2003 年， The Mathematical Intelligencer 杂志上发表了一篇题为 One hundred prisoners and a lightbulb 的论文，也让囚犯们正式引起了数学家们的关注。
Matrix67 |
2011-05-04 23:01 | 
