一个树林里有 100 个村庄，它们之间有 1000 条小路，每条小路都连接着两个不同的村庄。每条小路 e 都有一条难度系数 l(e) ，所有小路的难度系数都不相同。现在有一个探险家，他想要选择一条长度为 20 的路径，使得所经过的小路的难度系数不断增加。求证：他总能找到这样的路径。
探险家可以任意选择路径的起点和终点。
算法
跨越千年的RSA算法
数论，数学中的皇冠，最纯粹的数学。早在古希腊时代，人们就开始痴迷地研究数字，沉浸于这个几乎没有任何实用价值的思维游戏中。直到计算机诞生之后，几千年来的数论研究成果突然有了实际的应用，这个过程可以说是最为激动人心的数学话题之一。最近我在《程序员》杂志上连载了《跨越千年的 RSA 算法》，但受篇幅限制，只有一万字左右的内容。其实，从数论到 RSA 算法，里面的数学之美哪里是一万字能扯完的？在写作的过程中，我查了很多资料，找到了很多漂亮的例子，也积累了很多个人的思考，但最终都因为篇幅原因没有加进《程序员》的文章中。今天，我想重新梳理一下线索，把所有值得分享的内容一次性地呈现在这篇长文中，希望大家会有所收获。需要注意的是，本文有意为了照顾可读性而牺牲了严谨性。很多具体内容都仅作了直观解释，一些“显然如此”的细节实际上是需要证明的。如果你希望看到有关定理及其证明的严格表述，可以参见任意一本初等数论的书。把本文作为初等数论的学习读物是非常危险的。最后，希望大家能够积极指出文章中的缺陷，我会不断地做出修改。
======= 更新记录 =======
2012 年 12 月 15 日：发布全文。
2012 年 12 月 18 日：修改了几处表达。
2021 年 9 月 13 日：根据 Chang 的指正做了修改。
======== 目录 ========
（一）可公度线段
（二）中国剩余定理
（三）扩展的辗转相除
（四）Fermat 小定理
（五）公钥加密的可能性
（六）RSA 算法
趣题：由0和1构成的虫子
有一条虫子，它的整个身体由 n 节构成，每一节要么是有瑕疵的 1 ，要么是没有瑕疵的 0 ，因而整个虫子的身体结构就可以用一个 n 位 01 串来表示。你的目标是把整个虫子变成 000…00 的完美形式。每一次，你可以砍掉虫子最右侧的一节，同时虫子会在最左侧长出新的一节，以保持虫子的总长度不变。如果你砍掉的是一个 1 ，那么你可以指定虫子在最左侧长出的是 1 还是 0 ；但如果你砍掉的是一个 0 ，那么你无法控制虫子会在最左侧长出什么——它可能会长出 0 ，也可能会长出 1 ，因而你不得不假定，概率总是会和你做对，上天会竭尽全力地阻挠你。我们的问题是：不管虫子的初始状态是什么，你总能保证在有限步之内让虫子变成 000…00 吗？
注意，这个问题可能没有你想的那么简单。显然，我们必须得把一些 1 变成 0 ，这样才能让 1 的数目逐渐减少并最终消失。但是，如果只是简单地每次都把 1 变成 0 ，最终也不见得就一定能取胜。比如，如果这条虫子是 101 ，那么去掉最右边的 1 并选择在左边长出一个 0 ，虫子会变成 010 ；再把 010 右边的 0 去掉后，如果不巧左边长出的是 1 ，那么整条虫子又会回到 101 的状态。如此反复，将永远也不能得到 000 。而更加聪明的方法则是先把 101 变成 110 ，下一步虫子将会变成 111 或者 011 ，不管是哪种情况，接下来只需要逐个把 1 变成 0 就能获胜了。运用恰当的策略才能走到终点，这无疑让问题变得更加有趣。
互联网时代的社会语言学：基于SNS的文本数据挖掘
今年上半年，我在人人网实习了一段时间，期间得到了很多宝贵的数据，并做了一些还算有意义的事情，在这里和大家一块儿分享。感谢人人网提供的数据与工作环境，感谢赵继承博士、詹卫东老师的支持和建议。在这项工作中，我得到了很多与众人交流的机会，特别感谢 OpenParty 、 TEDxBeijing 提供的平台。本文已发表在了《程序员》杂志，分上下两部分刊于 2012 年 7 月刊和 8 月刊，在此感谢卢鸫翔编辑的辛勤工作。由于众所周知的原因，《程序员》刊出的文章被和谐过（看到后面大家就自动地知道被和谐的内容是什么了），因而我决定把完整版发在 Blog 上，同时与更多的人一同分享。对此感兴趣的朋友可以给我发邮件继续交流。好了，开始说正文吧。
作为中文系应用语言学专业的学生以及一名数学 Geek ，我非常热衷于用计算的方法去分析汉语资料。汉语是一种独特而神奇的语言。对汉语资料进行自然语言处理时，我们会遇到很多其他语言不会有的困难，比如分词——汉语的词与词之间没有空格，那计算机怎么才知道，“已结婚的和尚未结婚的青年都要实行计划生育”究竟说的是“已／结婚／的／和／尚未／结婚／的／青年”，还是“已／结婚／的／和尚／未／结婚／的／青年”呢？这就是所谓的分词歧义难题。不过，现在很多语言模型已经能比较漂亮地解决这一问题了。但在中文分词领域里，还有一个比分词歧义更令人头疼的东西——未登录词。中文没有首字母大写，专名号也被取消了，这叫计算机如何辨认人名地名之类的东西？更惨的则是机构名、品牌名、专业名词、缩略语、网络新词等等，它们的产生机制似乎完全无规律可寻。最近十年来，中文分词领域都在集中攻克这一难关。自动发现新词成为了关键的环节。
挖掘新词的传统方法是，先对文本进行分词，然后猜测未能成功匹配的剩余片段就是新词。这似乎陷入了一个怪圈：分词的准确性本身就依赖于词库的完整性，如果词库中根本没有新词，我们又怎么能信任分词结果呢？此时，一种大胆的想法是，首先不依赖于任何已有的词库，仅仅根据词的共同特征，将一段大规模语料中可能成词的文本片段全部提取出来，不管它是新词还是旧词。然后，再把所有抽出来的词和已有词库进行比较，不就能找出新词了吗？有了抽词算法后，我们还能以词为单位做更多有趣的数据挖掘工作。这里，我所选用的语料是人人网 2011 年 12 月前半个月部分用户的状态。非常感谢人人网提供这份极具价值的网络语料。
IMO2012趣题：带有说谎的猜数游戏
考虑一个传统的猜数游戏。 A 、 B 两名玩家事先约定一个正整数 N ，然后 A 在心里想一个不超过 N 的正整数 x ， B 则需要通过向 A 提问来猜出 A 心里想的数。 B 的问题只有唯一的格式：先列出一些数，然后问 A “x 是否在这些数里”， A 则需要如实回答“是”或者“否”。显然， B 是保证能猜到 x 的，只需要依次询问“x 是否等于 1 ”，“x 是否等于 2 ”即可。由于 B 可以精心选出满足某种特征的所有数，询问 x 是否在这些数里，因而 B 还可以做得更好。例如当 N ＝ 16 时， B 第一次可以问“x 是否小于等于 8 ”，或者等价地，“x 是否属于 {1, 2, 3, 4, 5, 6, 7, 8} ”；接下来，根据 A 的回复继续细问“x 是否小于等于 4 ”或者“x 是否小于等于 12 ”，以此类推。另一种方法则是询问“x 的二进制表达的第一位是否是 1”，“x 的二进制表达的第二位是否是 1”，以此类推，从而获得 x 的二进制表达的所有数位，便能推出 x 来。
现在，有意思的问题来了。假设 A 可以偶尔说谎（但保证不会连续说谎两次），那么 B 还能通过询问猜出 A 所想的数吗？如果愿意的话， B 可以询问任意多次。