如果把 3 · n + 1 问题改为 3^x · n + 1 问题

2016 年 5 月 2 日2016-05-03 / 53 条评论

Collatz 猜想也叫做 3 · n + 1 问题。这可能是数学中最为世人所知的未解之谜。它是如此初等，连小学生都能听懂它的内容；但解决它却如此之难，以至于 Paul Erdős 曾说：“或许现在的数学还没准备好去解决这样的问题。”这究竟是一个什么样的问题呢？让我们来看一下 Collatz 猜想的叙述：

任意取一个正整数 n 。如果 n 是奇数，则把 n 变为 3 · n + 1 ；如果 n 是偶数，则把 n 变为 n/2 。不断重复操作，则最终一定会得到 1 。

举个例子，如果 n = 26 ，那么经过下面 10 步之后，它最终变为了 1 ：

26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Collatz 猜想说的就是，这个规律对于所有正整数 n 均是如此。这个问题看起来是如此简单，以至于无数的数学家都掉进了这个坑里。光从这个问题的众多别名，便能看出这个问题害人不浅： Collatz 猜想又叫做 Ulam 猜想、 Kakutani 问题、 Thwaites 猜想、 Hasse 算法、 Syracuse 问题……研究这个问题的人很多，解决这个问题的人却一个没有。后来，人们干脆把它叫做 3 · n + 1 问题，让哪个数学家也不沾光。

这个问题有多难呢？我们可以从下面的这个例子中略见一斑。虽然从 26 出发只消 10 步就能变成 1 ，但若换一个数，比如 27 ，情况就大不一样了：

27 → 82 → 41 → 124 → 62 → 31 → 94 → 47 → 142 → 71 → 214 → 107 → 322 → 161 → 484 → 242 → 121 → 364 → 182 → 91 → 274 → 137 → 412 → 206 → 103 → 310 → 155 → 466 → 233 → 700 → 350 → 175 → 526 → 263 → 790 → 395 → 1186 → 593 → 1780 → 890 → 445 → 1336 → 668 → 334 → 167 → 502 → 251 → 754 → 377 → 1132 → 566 → 283 → 850 → 425 → 1276 → 638 → 319 → 958 → 479 → 1438 → 719 → 2158 → 1079 → 3238 → 1619 → 4858 → 2429 → 7288 → 3644 → 1822 → 911 → 2734 → 1367 → 4102 → 2051 → 6154 → 3077 → 9232 → 4616 → 2308 → 1154 → 577 → 1732 → 866 → 433 → 1300 → 650 → 325 → 976 → 488 → 244 → 122 → 61 → 184 → 92 → 46 → 23 → 70 → 35 → 106 → 53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

可见，当 n 的值不同时，从 n 变到 1 的路子是很没规律的。

有趣的是，如果我们把 Collatz 猜想中的乘以 3 改为乘以任意一个 3^x （其中 x 的值可由你自由选择），那么 Collatz 猜想就是正确的了。下面我们就来证明这一点。

26 个比较概率大小的问题

2016 年 4 月 27 日2016-04-29 / 52 条评论

你的数学直觉怎么样？你能凭借直觉，迅速地判断出谁的概率大，谁的概率小吗？下面就是 26 个这样的问题。如果你感兴趣的话，你可以先扫一遍所有的问题，再逐一阅读答案，看看你猜对了多少。这篇文章很长，你可以考虑把它加入书签，每天看几个问题。

1．A 、 B 、 C 、 D 四人玩扑克牌游戏， A 、 C 两人同盟， B 、 D 两人同盟。将除去大小王的 52 张牌随机分发给四人（每人获得 13 张牌）后，下面哪种情况的可能性更大一些？

A．A 、 C 两人手中都没有梅花
B．A 、 C 两人手中囊括了所有的梅花
C．上述两种情况的出现概率相同

A 、 C 两人手中都没有梅花，等价于 B 、 D 两人手中囊括了所有的梅花，它的概率与 A 、 C 两人手中囊括所有梅花的概率相同。因此，这个问题的答案显然是 C 。

UyHiP 趣题：出现次数最多的诱导子图

2016 年 3 月 1 日 / 10 条评论

下面这道题目是 Using your Head is Permitted 谜题站 2015 年 12 月的题目。

若干个顶点（vertex）以及某些顶点对之间的边（edge）就构成了一个图（graph）。下面就是这篇文章里会用到的四个图。其中，第一个图是由 2 个顶点组成的路径（path），因而我们把它称作 P₂ ；第二个图是由 3 个顶点组成的路径，因而我们把它称作 P₃ 。第三个图是由 3 个顶点组成的一个环（cycle），因而我们把它称作 C₃ ；第四个图是由 4 个顶点组成的一个环，因而我们把它称作 C₄ 。

选取图中的一个或多个顶点，同时选出这些顶点之间的所有边，得到的就是原图的一个“诱导子图”（induced subgraph）。在这篇文章中，我们只考虑那些连通的诱导子图。下面是一个有 6 个顶点的图，右边则列出了由它可以产生出来的所有连通诱导子图。注意，由于有些诱导子图不是连通的（比如只选择正上方的两个点和右下角的两个点，或者干脆只选择最左边那个点和最右边那个点），因而它们并没有在右边列出。在这些连通诱导子图里，很多图的本质都是相同的。比方说，第一行最后三个图和第二行前面四个图的本质是一样的，它们都是刚才我们介绍过的 P₂ 。当然，第一行的前六个图的本质也都是一样的，即由单个顶点构成的图，有时会被人们记作 K₁ 。观察最后一行的倒数第二个和倒数第三个图，你能看出这两个图的本质也一样吗？只不过，它们就没有什么固定的名字了。在这些连通诱导子图里，哪一种图出现的次数最多呢？答案就是 P₃ ，它一共出现了 8 次。

我们的问题是：能否构造一个图，使得里面出现次数最多的连通诱导子图是 C₃ ？能否构造一个图，使得里面出现次数最多的连通诱导子图是 C₄ ？注意，如果两种连通诱导子图出现的次数一样多，那它们都不算出现次数最多的连通诱导子图。

怎样把一个立方体分成 54 个小立方体？

2015 年 9 月 14 日 / 36 条评论

大家或许都听说过一个与正方形剖分相关的非常经典的问题：对于哪些正整数 n ，我们可以把一个正方形分割成 n 个小正方形（允许出现大小相同的小正方形）？答案是，除了 n = 2, 3, 5 以外，对于其他所有的 n ，把一个正方形分割成 n 个小正方形都是有可能的。对于 n = 1, 4, 6, 7, 8 的情况，分割方案如下图所示：

对于更大的 n 呢？注意到，每次用横竖两条线把一个小正方形分成四个更小的小正方形后，我们都会让这个图形里的正方形数目增加 3 个。因此，我们只需要在 n = 6 的方案上增加两笔，就能得到一个 n = 9 的方案；只需要在 n = 7 的方案上增加两笔，就能得到一个 n = 10 的方案；只需要在 n = 8 的方案上增加两笔，就能得到一个 n = 11 的方案；只需要在 n = 9 的方案上增加两笔，就能得到一个 n = 12 的方案……于是，其他所有的情况都被我们解决了。

Keller 猜想与 12 维空间中的神构造

2015 年 9 月 7 日 / 14 条评论

在各种令人惊讶的数学事实当中，我最喜欢的类型之一便是，某个数学命题在二维空间、三维空间甚至四维空间当中都是成立的，但偏偏到了某个维度时，命题就不成立了。 Keller 猜想就是一个这样的例子。

同样大小的正方形平铺整个平面（比如像下图那样），则一定存在某些边与边完全贴合的相邻正方形。

类似地，同样大小的正方体平铺整个空间（比如像下图那样），则一定存在某些面与面完全贴合的相邻正方体。

1930 年， Ott-Heinrich Keller 猜测，或许这一点对于更高维度的空间都是成立的。也就是说， Ott-Heinrich Keller 猜测，对于任意正整数 n ≥ 2 都有，同样大小的 n 维立方体平铺整个 n 维空间，则一定有两个面与面完全贴合的相邻 n 维立方体。这就是著名的 Keller 猜想。

1940 年， Oskar Perron 证明了，当 n = 2, 3, 4, 5, 6 时， Keller 猜想确实是正确的。一切似乎都在正轨上。然而，到了 1992 年的时候，事情出现了转折： Jeffrey Lagarias 和 Peter Shor 构造了一个 n = 12 时的反例，从而推翻了 Keller 猜想。让我们来看一看 Lagarias 和 Shor 的神构造吧。为了方便起见，下面我们直接用“立方体”一词指代 n 维的广义立方体，“立方体的面”则代表 n 维立方体的 n – 1 维面。