幸福结局问题，以及一个幸福的结局

2011 年 5 月 4 日 / 42 条评论

今天是我第一次听说这个故事。

1933 年，匈牙利数学家 George Szekeres 还只有 22 岁。那时，他常常和朋友们在匈牙利的首都布达佩斯讨论数学。这群人里面还有同样生于匈牙利的数学怪才——Paul Erdős 大神。不过当时，Erdős 只有 20 岁。

在一次数学聚会上，一位叫做 Esther Klein 的美女同学提出了这么一个结论：在平面上随便画五个点（其中任意三点不共线），那么一定有四个点，它们构成一个凸四边形。Szekeres 和 Erdős 等人想了好一会儿，没想到该怎么证明。于是，美女同学得意地宣布了她的证明：这五个点的凸包（覆盖整个点集的最小凸多边形）只可能是五边形、四边形和三角形。前两种情况都已经不用再讨论了，而对于第三种情况，把三角形内的两个点连成一条直线，则三角形的三个顶点中一定有两个顶点在这条直线的同一侧，这四个点便构成了一个凸四边形。

Kolakoski序列：我们知道的还是太少

2011 年 5 月 4 日 / 34 条评论

上帝创造了整数，其余的则是我们人类的事了。正因为如此，质数、完全数、Fibonacci 数之类的数列才会让数学家们如痴如醉，因为它们的存在是如此自然，没有任何人造的因素。事实上，数学家们对这些数的认识也越来越丰富，挖掘出了这些数列中越来越深刻的性质。

不过，人类确实太渺小了。还有好多构造异常简单的“纯天然数列”，我们了解得实在太少。Kolakoski 数列就是最好的例子之一。

Kolakoski 数列仅由 1 和 2 构成，其中头 100 个数是

1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1,
2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1,
1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2,
1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2,
2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, …

趣题：不动点与线性代数

2011 年 5 月 2 日 / 26 条评论

假设 X 、 Y 是两个有限集合，f:X→Y 和 g:Y→X 是两个函数。求证：复合函数 g∘f 和 f∘g 拥有相同数量的不动点（也就是说 g(f(x)) = x 和 f(g(y)) = y 的解的个数相同）。

下面先提供一个“正常”的解法。观察函数 g∘f 的不动点，可以看出它有以下两个性质：首先，如果某个 x 是 g∘f 的不动点，即 x = g(f(x)) ，那么 f(x) = f(g(f(x)))，这就说明 f(x) 是 f∘g 的一个不动点；另外，如果 x₁ 和 x₂ 是 X 中两个不同的不动点，则函数 f 不可能把它们映射到 Y 中的同一个元素，否则 g 没办法把它分别还原成 x₁ 和 x₂ 。结合上面两点可以看出， f∘g 中的不动点至少和 g∘f 的一样多。

同理，考察 f∘g 的不动点，可知 g∘f 的不动点至少和 f∘g 的一样多。这就说明了 g∘f 和 f∘g 拥有相同数量的不动点。