这个月月初就开始看《从一到无穷大》，花了接近两个星期才看完。这确实是一本让人放不下手的好书。考虑到我的阅读速度，一个多星期一本书已经近乎神速了。在这本书里我经常会看到一些有趣的数学知识，前段时间我还写过书里提到的一个有趣的东西——环面上的染色问题反而比平面上的“四色问题”更加简单。这种例子并不罕见，很多时候一些扩展版的问题反而比原问题更加简单。在第八章，我看到了另一个好玩的东西：随机游走(random walk)问题。
    随机游走问题是说，假如你每次随机选择一个方向迈出一个单位的长度，那么n次行动之后你离原点平均有多远（即离原点距离的期望值）。有趣的是，这个问题的二维情况反而比一维情况更加简单，关键就是一维情况下的绝对值符号无法打开来。先拿一维情况来说，多数人第一反应肯定是，平均距离应该是0，因为向左走和向右走的几率是一样的。确实，原点两边的情况是对称的，最终坐标的平均值应该是0才对；但我们这里考虑的是距离，它需要加上一个绝对值的符号，期望显然是一个比0大的数。如果我们做p次实验，那么我们要求的平均距离D就应该是

    其中d的值随机取1或者-1。这里的绝对值符号是一个打不破的坚冰，它让处于不同绝对值符号内的d值无法互相抵消。但是，当同样的问题扩展到二维时，情况有了很大的改变。我们把每一步的路径投射到X轴和Y轴上，利用勾股定理我们可以求出离原点的距离的平方R^2的值：

    一旦把平方展开后，有趣的事情出现了：这些X值和Y值都是有正有负均匀分布的，因此当实验次数p充分大时，除了那几个平方项以外，其它的都抵消了。最后呢，式子就变成了

    于是呢，就有平均距离R=sqrt(n) （准确的说是均方根距离）。我们得出，在二维平面内随机选择方向走一个单位的长度，则n步之后离出发点的平均距离为根号n。这是一个很美妙的结论。

查看更多 »

    想当年搞竞赛那会儿，我真是读了不少书，收获相当大。进大学后渐渐地淡出了竞赛的世界，于是开始看各种类型的数学书。Pólya的几本牛书陪伴我熬过了无聊的古代汉语课和现代文学史课，每个星期消化一点《什么是数学》已经成了一种习惯。最近笔记本的电池越来越不能扛了，熄灯后最多挺一个半小时。那要是笔记本没电了我该干啥呢？于是在网上买了个平板阅读灯，等寝室的人都睡了之后安安静静地伏在床上看书、思考。想看的书真是多啊……偏偏我看书又慢。正在看《苏菲的世界》，《三体II》还没看，昨天又买了一大堆书……真希望我能有更多的时间来看书。

Sofies verden / Sophie's World / 苏菲的世界
    这是一本异常奇特的小说，也是一本绝佳的哲学史入门读物。最早我是在Wikipedia的self reference词条下知道这本书的，因为这本小说中的主人公最终发现自己是一本小说中的主人公。现在正在看这本书，马上要看完了。我看书是出了名的慢，断断续续地看了一个假期都还没看完。

Kabalmysteriet / The Solitaire Mystery / 纸牌的秘密
    和Stetson MM聊得最火热的那段时间里，我曾经提到过我要看《苏菲的世界》。Stetson MM告诉我说，《苏菲的世界》她没看过，但是同一作者的另一本书《纸牌的秘密》她看过的，并且她非常强烈地向我推荐这本书。前几天看到她校内上的日志还引用了《纸牌的秘密》里面的话。

The Cat Who Walks Through Walls / 穿墙猫
    科幻大师Robert A. Heinlein的一部科幻小说。我是相当喜欢Heinlein的了，《你们这些还魂尸》是我见过的最牛B的时间悖论题材的科幻小说。The Cat Who Walks Through Walls也是我在Wikipedia的self reference词条下看到的，它上面介绍说，这本书considers the universe as an author-manipulated object including the plot in the book itself，想必应该会相当有趣吧。目前这本书好像没有中译。

One Two Three... Infinity / 从一到无穷大
The Emperor's New Mind / 皇帝新脑
    这两本书是相当经典的了，我居然还没读过-_-b
    刚刚把这两本书买了，看完苏菲就看它们俩。

查看更多 »

    Proofs from THE BOOK的第六章相当精彩，这一章循序渐进地介绍了多个无理性证明。先证明e是无理数，证明方法和高数课本上的基本相同；试图用类似的办法证明e^2也是无理数时，这一章的内容开始牛B了起来，一些巧妙的变换就让原来的办法继续适用于e^2的证明；加上一些更有趣的技巧，我们还能继续证明e^4也是无理数；当证明对除0外的所有有理数r，e^r都是无理数时，全章达到了高潮。
    这一章还提到了pi^2是无理数的证明方法。这个证明建立在Ivan Niven于1947年提出的“pi是无理数”的经典证明的基础上：仅仅是在原证明过程中加了一些微妙的变化就得到了pi^2也是无理数的结论。注意到，“pi^2是无理数”是一个比“pi是无理数”更强的结论。由于有理数的平方还是有理数，因此证到了pi^2是无理数也就说明了pi必然是无理数；但反过来却不行，因为无理数的平方不一定也是无理数，比如根号2的平方就不是无理数。

    证明过程用到了一个函数，其中n是一个任取的大于等于1的常数。可以想像，这个函数的分子部分展开后是一个关于x的整系数多项式，最低次数为n，最高次数为2n。我们将用到这个函数的两个性质：首先，当0<x<1时，显然有0 < f(x) < 1/n!；其次，函数f及其任意阶导数在x=0和x=1处都是整数。为了证明后一个结论，首先注意到当x=0时，不管是多少阶的导数，除了常数项以外其余项都是0；常数项只可能在n<=k<=2n时出现（k表示k阶导数），但此时它等于一个整系数乘以k!/n!，显然也是个整数。另外，由于f(x)=f(1-x)，根据复合函数的微分法我们立即得到对任意x都成立，当然也就有。

查看更多 »

    又回来更新啦！虽然还有两门课没考，但今天已经轻松了不少。梦魇般的现代文学史总算是结束了。抱了两天两夜的佛脚，结果考试时一看卷子，仍然没一道会的题目。不定项选择多选少选均不得分，都是些文学常识题，给四篇我从没见过的小说名字问哪些是第一人称叙事，或者给四个人名字问哪些是笔名之类的。天哪……以后的古代文学史咋办啊。
    先强烈推荐一本好书。前几天在TopLanguage看到有牛人推荐Proofs from THE BOOK这本书，当即决定买了下来。这几天复习累了我都在看这本书，真的是很好很强大，里面汇集了很多著名问题的经典证明，包括很多我一直想找但没找到的证明。好了不多废话了，下面进入正题。

    很早以前，我们曾经研究过质数，证明了质数有无穷多个。后来，我们又学到了另外两种证明质数无穷多的方法。这两种方法的基本思路相同：寻找一个无穷大的集合，里面的数两两互质。只用有限个质数明显不能得到无穷多个两两互质的数，于是我们立即可知质数必然有无穷多个。今天，我们将证明两个比质数无穷多更强的定理。这两个证明都出自Proofs from THE BOOK的第一章。

    定义函数π(x)为“小于等于x的质数有多少个”。无妨规定x为一个正整数。我们将用初等微积分方法证明当x趋于无穷时π(x)也趋于无穷并给出π(x)的一个下界。我们将说明，对于所有x，π(x)>=log(x)-1，即x以内的质数至少有log(x)-1个。
    为了说明这一点，让我们考虑所有不超过x的质数的倒数的等比级数(1 + 1/p + 1/p^2 + ..)的乘积，即。
    回忆等比级数的公式，则我们有：

    第二行的一些变换非常巧妙。第二行中间的不等号是一个关键，用到了一个基本事实：第k个质数显然比k大。最后的连乘中前一项的分子和后一项的分母正好抵消，最后消完了就只剩了一个π(x)+1。
    另一方面，想像一下把(1+1/2+1/4+...)(1+1/3+1/9+...)(1+1/5+1/25+...)...展开的样子，很显然展开后的每一项都是一个所有质因子都不大于x的数的倒数，即Σ(1/m)，其中m取所有仅含1..x范围内的质因子的数。显然，原本就比x小的数，其质因子当然不可能超过x，这就是说从1到x的所有正整数都是属于m的。利用一些微积分的基本知识，我们可以立即得出Σ(1/m) >= 1+1/2+1/3+...+1/x >= log(x)。地球人都知道，log(x)是没有上界的，于是质数的个数也没有上界。
    这里还有一个类似的问题，大家可以对照着看看。

查看更多 »

    今天，我们将从一系列公理开始，从自然数的产生一直说到实数理论的完善。你或许会对数学的“科学性”有一个新的认识。注意，本文的很大一部分内容并非直接来源《什么是数学》，这篇文章可以看作是《什么是数学》中有关章节的一个扩展。

    自然数是数学界中最自然的数，它用来描述物体的个数，再抽象一些就是集合的元素个数。在人类文明的最早期，人们就已经很自然地用到了自然数。可以说，自然数是天然产生的，其余的一切都是从自然数出发慢慢扩展演变出来的。数学家Kronecker曾说过，上帝创造了自然数，其余的一切皆是人的劳作。 (God made the natural numbers; all else is the work of man.)
    随着一些数学理论的发展，我们迫切地希望对自然数本身有一个数学描述。从逻辑上看，到底什么是自然数呢？历史上对自然数的数学描述有过很多的尝试。数学家Giuseppe Peano提出了一系列用于构造自然数算术体系的公理，称为Peano公理。Peano公理认为，自然数是一堆满足以下五个条件的符号：
   1. 0是一个自然数；
   2. 每个自然数a都有一个后继自然数，记作S(a)；
   3. 不存在后继为0的自然数；
   4. 不同的自然数有不同的后继。即若a≠b，则S(a)≠S(b)；
   5. 如果一个自然数集合S包含0，并且集合中每一个数的后继仍在集合S中，则所有自然数都在集合S中。（这保证了数学归纳法的正确性）

    形象地说，这五条公理规定了自然数是一个以0开头的单向有序链表。
    自然数的加法和乘法可以简单地使用递归的方法来定义，即对任意一个自然数a，有：
a + 0 = a
a + S(b) = S(a+b)
a · 0 = 0
a · S(b) = a + (a·b)

    其它运算可以借助加法和乘法来定义。例如，减法就是加法的逆运算，除法就是乘法的逆运算，“a≤b”的意思就是存在一个自然数c使得a+c=b。交换律、结合率和分配率这几个基本性质也可以从上面的定义出发推导出来。
    Peano公理提出后，多数人认为这足以定义出自然数的运算，但Poincaré等人却开始质疑Peano算术体系的相容性：是否有可能从这些定义出发，经过一系列严格的数学推导，最后得出0=1之类的荒谬结论？如果一系列公理可以推导出两个互相矛盾的命题，我们就说这个公理体系是不相容的。Hilbert的23个问题中的第二个问题就是问，能否证明Peano算术体系是相容的。这个问题至今仍有争议。

查看更多 »

    期中告一段落。除了下下星期要交的现文史论文以外，最近似乎又清闲了不少，又有功夫在这里写点东西了。当然，我宝贵的时间也没有荒废在论文、作业和考试上。几乎每一堂古汉课和现文史课我都在读《什么是数学》，进度算是相当快了。这可能是我近几年读的所有书中给我带来的收获最大的一本。最近好几个人问我，有什么牛B一点的数学书没。我毫不犹豫地脱口而出，《什么是数学》。如果我要去一个荒岛上，只能带三本书，我会选择《算法导论》、《组合数学》和《什么是数学》。如果叫我舍弃一样，我估计会扔掉《组合数学》。如果还得再丢弃一本，我只好忍痛丢下《算法导论》了。
    读《什么是数学》的收获太多了。在这里，我只更新一些我原来不知道，又很有趣的东西。如果你希望迅速对此书有一个全面的了解，千万不要错过dd牛的《什么是数学》笔记。

    阅读《什么是数学》的前面几章时，你经常会跟随着书中的文字重新看待一个显而易见的结论，然后对这个结论有了一个全新的认识。比如，书中曾提到，为什么数学归纳法是合理的？我已经知道n=1时结论成立，也知道若n=k成立则n=k+1结论也成立，那么对于任意一个给定的正整数t，n=t时的结论是成立的，因为经过有限次迭代后最终我们总可以到达n=t的情况。但是，为什么我们敢断言对所有这无穷多个n，结论都是成立的？显然，你不能说“我们可以迭代无穷多次”，一个有限的证明过程当然不允许有无限多个步骤。因此，为了说明对于所有正整数n结论都成立，我们不得不使用反证法把“无穷”变成“有穷”。我们假设对于某些n，这个结论是不成立的。那么，这里面一定存在一个最小的数p，它使得结论不成立。由于我们已知n=1时结论成立，因此p一定是大于1的。但n=p是“最早”使结论不成立的情形，因此n=p-1时结论一定为真。这就与我们已知的第二个条件“若n=k成立则n=k+1结论也成立”矛盾了。因此我们说，对于所有正整数n，结论都是成立的。
    这个推理过程中用到了另一个显而易见的结论：对于一个非空的正整数集C，C中一定存在一个最小的元素。这又是为什么呢？你可能会说，废话，把所有元素拿出来两个两个的比，一定能比出一个最小的数来。这种说法是错误的。注意到集合C有可能有无穷多个元素，你是比不完的。为了更清晰地认识这个结论，我们只需要注意到，如果把条件换成“有理数集C”或者“实数集C”，结论就不再成立了，因为集合{1, 1/2, 1/3, 1/4, ...}显然不存在一个最小的数。可以看到，上述结论是否成立是和数的稠密性紧紧相关的。事实上，为了说明正整数集C中存在最小元素，我们任意从集合中取出一个元素n，那么1, 2, ..., n这有限多个数当中一定存在一个最小的数，它在这个集合C中。它就是整个集合的最小数。对于稠密的有理数点和实数点，这个证明显然不再适用。
查看更多 »

    每个领域里都有那么几本经典的读物，比如科幻界的圣经就是世界科幻之父Jules Verne的一系列作品，或是家喻户晓的科幻经典Hitchhiker's Guide to the Galaxy；信息学界则有Knuth的The Art of Computer Programming，或是每个搞OI/ACM的都看过或者听说过的Introduction to Algorithms。前段时间有数学爱好者在这里留言问到有没有什么好的数学书，在这里我和大家分享几本数学界的经典读物。

    有史以来最为经典的数学书当属What Is Mathematics? An Elementary Approach to Ideas and Methods（中译：什么是数学？对思想和方法的基本研究）。这本书由Courant和Herbert Robbins所写，后来Ian Stewart做了修订，增加了一些Courant和Robbins时代还没有的新进展。这本书非常牛B，Einstein曾说，这本书是“对整个数学领域中的基本概念及方法的透彻清晰的阐述”。
    Ian Stewart自己也写过不少书，他似乎很喜欢把数学和其它自然科学联系在一起，比较经典的是Nature's Numbers（中译：大自然的数学游戏）；另一本经典则是Does God Play Dice，不过我既没找到中译本，也没找到影印版。

    前几天数学课上我们老师推荐了Pólya的几本经典著作：

• How to Solve It: A New Aspect of Mathematical Method
  
• Mathematics and Plausible Reasoning: Volume I Induction and Analogy in Mathematics
  
• Mathematics and Plausible Reasoning: Volume II Patterns of Plausible Inference

    这三本书现在都有译本，中译名分别如下：

• 怎样解题：数学思维的新方法
  
• 数学与猜想（第一卷）：数学中的归纳和类比
  
• 数学与猜想（第二卷）：合情推理模式

    现在我正在看《数学与猜想》，里面的习题设置是一大亮点。读完一章后你一定要认真完成所有的习题，不然你这本书就白买了。每一章的习题都是前后连贯，一气呵成的。前面的题可以帮助你完成后面的题，带你一步一步进行发现、归纳、猜想、验证和证明。依次完成这一章的所有习题后你会体会到探索数学奥秘的乐趣。以后只要我发现这些书里有什么我从没见过的新奇玩意儿，我都会放到Blog上。

    探索数学世界，看一本数学史书是很有必要的。我曾专门去书店找过，这一类的书有很多，比如机械工业出版社就有一本Victor J.Katz的数学简史。早以前我买了一本《数学悖论与三次数学危机》，这本书则从一个特殊的角度纵观数学发展史，切入点非常有意思。

    国外还有很多非常流行的数学科普读物，这些书曾经非常畅销。例如，John Allen Paulos的Once Upon a Number: The Hidden Mathematical Logic of Stories（中译：从前有个数：故事中的数学逻辑）就是一本很流行的大众化数学读物；而另类科幻小说Flatland（中译：神奇的二维国）则以一个特殊的形式向大家介绍了数学中的维度概念。

最后，欢迎大家在下面留言，给我和其它网友也推荐一些好的数学书
Matrix67原创，转贴请注明出处

    近来有很多问该看什么书的。我说一下个人意见（仅代表个人意见）。大家可以按照这样的顺序来阅读这些书（时间足够的话）：

    《算法导论》
    《数据结构与算法分析——C语言描述》
    《组合数学》

    这三本书必看，都是机械工业出版社出版的，翻译质量嘛——尽管有些别扭（翻译的东西都这样），但肯定看得懂。
    第一本的中译本是才出版的，比原来那个盗版的要好得多。
    第二本是Mark Allen Weiss写的，第二版。
    第三本是Richard A.Brualdi写的，第四版。
    如果你英文好的话，最好看原版。
    有人会问我为什么喜欢国外的教材。这是因为，国外的教材各个章节安排得很好，体系性更强，看起来更轻松（保证你能看懂），而且更具有启发性。这些教材的习题安排得很好，绝对是可以经过独立思考想出来的题目。和国内很多教材扔出一大堆概念和公式不同，阅读国外教材是循序渐进的一个学习过程。

    以下两本书的话，有兴趣就看吧。
    《离散数学》，第六版，Richard Johnsonbaugh，电子工业出版社。
    《How to Ace Calculus: The Streetwise Guide》系列，中译本叫做“微积分之XXXX”，湖南科学技术出版社。当成看小说吧，很有意思，是我见过的最不像教材的教材了。

    最后需要看的是刘汝佳和黄亮的《算法艺术与信息学竞赛》。这里面有很多概念上的讲解是错误的，但是题目讲解的资源很丰富。当前面的书看完了后，拿最后这一本当作题库来实战演练吧。书里的概念讲解部分就不必看了，直接消化里面的例题，一道一道地消化。第三部分的计算几何可以仔细学习一下，因为这部分内容之前的书好像涵盖得不多。

    还有，选择什么样的题库。个人首推USACO。大家可以自己了解一下这个与众不同的OJ，它基本上是一个“个人的教练”，并不参与网络排名。你大概需要话半年的时间完成所有的题目。做USACO需要你的认真态度和耐心。千万别看中译和别人的解答。整个USACO的任务完成之后，你基本上就无敌了。