《数学女孩》系列以小说的形式展开，重点描述一群年轻人探寻数学中的美。内容由浅入深，数学讲解部分十分精妙，被称为“绝赞的数学科普书”。

—— 图灵新知 (opens new window)

# 数学女孩 1-6 大纲

  • 《数学女孩》：由浅至深讲解了等比数列、泰勒展开、 无穷级数、生成函数、卷积、调和数、分拆数等知识
  • 《数学女孩2：费马大定理》：以勾股定理、最大公因数和最小公倍数、群论、无限递降法为铺垫，讲解了费马大定理（在 n=4n=4 的证明过程，和 n>=3n >= 3 时的证明路线）
  • 《数学女孩3：哥德尔不完备定理》：以逻辑判断题、皮亚诺公理、集合与无限、极限、逻辑学、形式系统铺垫，讲解了哥德尔不完备定理的证明过程
  • 《数学女孩4：随机算法》：以排列组合、概率、线性代数、算法作为铺垫，讲解了 3-SAT 问题的随机算法，以及分析了快速排序、随机选取枢纽的快速排序算法的时间复杂度
  • 《数学女孩5：伽罗瓦理论》：以群、域、二次方程的根系关系、向量空间作为铺垫，讲解了三次方程通解、作图三等分角问题、多项式方程可解问题（伽罗瓦理论）的推导

# 摘抄

# 学习和研究的不同

我有时候在想，学习和研究到底有何不同呢?
数学课上，只要读读教科书上写着的内容，然后记住公式， 再用记住的公式解开问题，对一下答案就结束了。
然而我认为，研究是去探求“未知的答案”， 是向答案逼近的一个过程。 因为不知道答案才会有趣。 从自己找寻、发现答案的过程中， 才能感受到研究的魅力所在。
—— 山本裕子

——《数学女孩2：费马大定理》

# 曾经最先进的知识，现在也普及到初中高中了

“费马大定理没有第二种证法吗？”泰朵拉问道。
“没有初级的证法。”走在最前面的米尔嘉回过头，“数学家们这么说的。那就是肯定没有。不过今后可能会发现新的数学概念，从而创造出更简便的证法。”
就像发现“负数”那样？
就像发现“复数”那样？
“真能发现吗？”泰朵拉问道。
“逆用勾股定理，就能创造出直角。这是当时最尖端的技术，但是现在已经在小学普及了。二次方程的解法、复数、矩阵、微积分……所有这些都是曾经最先进的知识，不过现在也普及到初中高中了。这样下去没准以后我们在学校就能学到‘费马大定理的证法’。”
“原来如此……”泰朵拉点点头。
“我们只活在当下。”米尔嘉继续道，她的脸颊冻得发红，“然而，散布在历史这条时间轴上的无数数学知识，都投射到了‘现在’这一点上。我们学的就是这一点上的投影。”

——《数学女孩2：费马大定理》10.8 节

# Q. E. D.

Q.E.D. 是拉丁片语 Quod Erat Demonstrandum（意思是“这就是所要证明的”）的缩写。这句拉丁片语译自希腊语，包括欧几里得和阿基米德在内的很多早期数学家都用过。

——《数学女孩 3：哥德尔不完备定理》

# 为什么证明整数相关性质，总会用到数学归纳法

不管要证明整数的何种性质，
都必须在某处用到数学归纳法。
因为，只要追溯至基本概念就会发现，
整数本质上是通过数学归纳法定义的。 —— 高德纳

——《数学女孩 3：哥德尔不完备定理》2.4.2 节

# 拓展全新的概念时，每个人都会犹豫

17世纪，伽利略认为，在“无限”这个条件下，不能说个数在双射中是相等的，于是在此处折返。

19世纪，康托尔和戴德金也发现了这个数学事实，但他们并没有像伽利略这么想。戴德金认为，整体和部分之间存在双射，正是无限的定义。这是一场惊人的思维大颠覆。

出错了、不合逻辑 —— 之所以会陷入这种泥潭，是因为碰上了前所未有的概念。
我们可以认为自己失败了，然后折返。
不过，我们也可以认为这是一个新的发现，然后继续前进。

拓展概念时的困难就在于“飞跃前的停滞”。每个人都会犹豫，这种犹豫经常会体现在数的命名上。
负数 - Negative Number - 否定的
无理数 - Irational Number - 不合理的
虚数 - Imaginary Number - 想象中的
否定的，不合理的，想象中的……这些英语单词充分体现了人类面对全新概念时产生的犹豫。要向新的道路前进时，任谁都会犹豫啊。

——《数学女孩 3：哥德尔不完备定理》3.3.2 节

# 新概念会迅速和已有的数学工具融合

即使数学新引入了一个抽象的概念，
只要明确定义了这个概念，
那么就算它看似漂浮于虚空之中，
也会立即化身成集合与其元素，飘落到地面上，
随之混入各种各样的数学之中，朝气蓬勃地开始发光发热。
——志贺浩二，日本数学家

——《数学女孩 3：哥德尔不完备定理》

# 为什么讨论时不要关注含义，只关注形式

有时，如果人们在思考了含义的基础上进行论证，根据就会变得不明确，如果不去思考含义，只关注形式根据就会变得明确。因为不管怎么说，人们只会使用明确定义过的事物。

——《数学女孩 3：哥德尔不完备定理》

# 数学问题

# 0.999... = 1

注意这里的 ... 是一种记法，表示的是序列 0.9、0.99、0.999 无限延伸下去后接近的数，而非序列中的某一个数。故有：

0.999...=10.999... = 1
0.999...9<10.999...9 < 1

# 形式系统

之前没有学过形式系统，第二遍读《数学女孩 3：哥德尔不完备定理》的时候，就新开了一篇博客。

# 为什么数学里讨论骰子，总是假设“每一面出现的概率都相同”

“按相同的可能性发生”的情况是怎样的情况？对于这一问题，数学无法作出回答。

—— 柯尔莫哥洛夫《概率论导论》

通过概率公理 (opens new window)，将符合公理的函数称作概率分布函数，以此定义了概率，即公理概率。

古典概率是公理概率的特殊情况，其特殊之处就在于，古典概率需要基于“所有事件按相同的可能性发生”。当“所有事件发生的可能性不同”，讨论的问题就不是古典概率能解决的，但仍可以通过公理概率解决。

出现于《数学女孩 4》。

# 评估 n!n! 的近似值 —— 斯特林公式

斯特林公式 - 维基百科，自由的百科全书 (opens new window)

斯特林公式用于评估 n!n! 的近似值。它的精度非常高，即使 nn 很小，其取值也十分精确。出现于《数学女孩 4》，可用于证明比较排序算法的时间复杂度为 Ω(nlog⁡n)\Omega(n\log n)。

# “幸福的台阶”——一直掷 6 面骰子，直到掷出过所有面，掷骰子的期望次数

出现于《数学女孩 4》。

# 分解为子问题——“上台阶”

可以把丢出一个新数字看作上一个台阶，原事件等价于上六次台阶。

设“掷出所有点数时，掷骰子的次数”为 XX。又设“掷出 jj 种点数以后，直至丢出没出过的点数时，掷骰子的次数”为 XjX_j。显然有：

X=X0+X1+X2+X3+X4+X5E[X]=E[X0]+E[X1]+E[X2]+E[X3]+E[X4]+E[X5] \begin{aligned} X &= X_0 + X_1 + X_2 + X_3 + X_4 + X_5 \\ E[X] &= E[X_0] + E[X_1] + E[X_2] + E[X_3] + E[X_4] + E[X_5] \end{aligned}

# 研究子问题——“上一次台阶”的期望次数

现在讨论 E[Xi]E[X_i]。显然，E[X0]=1E[X_0] = 1。

掷一次骰子有两种情况：掷出没有出现过的点数、掷出已经出现的点数。对于已经出现过 jj 个点的情况，记

pj=P{掷出没有出现过的点数}=1−j6qj=P{掷出出现过的点数}=j6 \begin{aligned} p_j &= P \{ \text{掷出没有出现过的点数} \} = 1 - \frac{j}{6} \\ q_j &= P \{ \text{掷出出现过的点数} \} = \frac{j}{6} \end{aligned}

那么，XjX_j 可以被视为丢概率不同的硬币，丢出一次正面的期望丢硬币次数（非常漂亮的转化）。

要计算 E(Xj)E(X_j)，我们就分别计算 P(Xj=k)P(X_j = k)。貌似不可直接列表算，但是可以取极限（出现了，微积分！）。有

P(Xj=k)=qjk−1⋅pj=qjk−1⋅(1−qj)=qjk−1−qjk\begin{aligned} P(X_j = k) &= q_j^{k-1} \cdot p_j \\ &= q_j^{k-1} \cdot (1- q_j) \\ &= q_j^{k-1} - q_j^k \end{aligned}

则

E[Xj]=∑k=1∞k⋅P(Xj=k)=lim⁡n→∞∑k=1nk⋅P(Xj=k)=lim⁡n→∞∑k=1nk(qjk−1−qjk)=lim⁡n→∞(1⋅(qj0−qj1)+2⋅(qj1−qj2)+⋯n⋅(qjn−1−qjn))=lim⁡n→∞(1+qj1+qj2+⋯qjn−1−n⋅qjn)=lim⁡n→∞(1−qjn1−qj−n⋅qjn)=lim⁡n→∞[1−(j6)n1−j6−n⋅(j6)n]=11−j6=66−j \begin{aligned} E[X_j] &= \sum_{k=1}^{\infty} k \cdot P(X_j = k) \\ &= \lim_{n \to \infty} \sum_{k=1}^{n} k \cdot P(X_j = k) \\ &= \lim_{n \to \infty} \sum_{k=1}^{n} k (q_j^{k-1} - q_j^k) \\ &= \lim_{n \to \infty} ( 1 \cdot (q_j^0 - q_j^1) + 2 \cdot (q_j^1 - q_j^2) + \cdots n \cdot (q_j^{n-1} - q_j^n)) \\ &= \lim_{n \to \infty} ( 1 + q_j^1 + q_j^2 + \cdots q_j^{n-1} - n \cdot q_j^n) \\ &= \lim_{n \to \infty} \bigg( \frac{1-q_j^n}{1-q_j} - n \cdot q_j^n \bigg) \\ &= \lim_{n \to \infty} \bigg[ \frac{1- (\frac{j}{6})^n}{1-\frac{j}{6}} - n \cdot (\frac{j}{6})^n \bigg] \\ &= \frac{1}{1-\frac{j}{6}} \\ &= \frac{6}{6-j} \end{aligned}

# 回到原问题

结果就比较显然了。

E[X]=E[X0]+E[X1]+E[X2]+E[X3]+E[X4]+E[X5]=66+65+64+63+62+61=6H6≈14.7 \begin{aligned} E[X] &= E[X_0] + E[X_1] + E[X_2] + E[X_3] + E[X_4] + E[X_5] \\ &= \frac{6}{6} + \frac{6}{5} + \frac{6}{4} + \frac{6}{3} + \frac{6}{2} + \frac{6}{1} \\ &= 6H_6 \\ &\approx 14.7 \end{aligned}

其中 Hn=∑i=1n1iH_n = \sum_{i=1}^{n} \frac{1}{i} 为调和级数。

该问题还有通用结论：

一直掷 nn 面骰子，直到掷出过所有面，掷骰子的期望次数为：

n⋅Hn=n⋅∑i=1n1in \cdot H_n = n \cdot \sum_{i=1}^{n} \frac{1}{i}