Mathematics

WOM 编码与一次写入型存储器的重复使用

计算机历史上,很多存储器的写入操作都是一次性的。 Wikipedia 的 write once read many 词条里提到了两个最经典的例子,一个是大家熟悉的 CD-R 和 DVD-R ,另一个则是更早的打孔卡片和打孔纸带。在介绍后者时,文章里说:“虽然第一次打孔之后,没有孔的区域还能继续打孔,但这么做几乎没有任何实际用处。”因此,打孔卡片和打孔纸带通常也被看成是只能写入一次的存储设备。 事实上真的是这样吗? 1982 年, Ronald Rivest 和 Adi Shamir 发表了一篇题为《怎样重复使用一次写入型存储器》(How to Reuse a “Write-Once” Memory)的论文,提出了一个很有意思的想法。大家有觉得 Ronald Rivest 和 Adi Shamir 这两个人名都很眼熟吗?没错,这两个人之前曾经和 Leonard Adleman 一道,共同建立了 RSA 公钥加密系统。其中, Ronald Rivest 就是 RSA 中的那个 R , Adi Shamir 就是 RSA 中的那个 S 。 在这篇论文的开头, Ronald Rivest 和 […]

Mathematics

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

大家或许都听说过一个与正方形剖分相关的非常经典的问题:对于哪些正整数 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 […]

Mathematics

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

在各种令人惊讶的数学事实当中,我最喜欢的类型之一便是,某个数学命题在二维空间、三维空间甚至四维空间当中都是成立的,但偏偏到了某个维度时,命题就不成立了。 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 […]

Mathematics

用三段 140 字符以内的代码生成一张 1024×1024 的图片

Kyle McCormick 在 StackExchange 上发起了一个叫做 Tweetable Mathematical Art 的比赛,参赛者需要用三条推这么长的代码来生成一张图片。具体地说,参赛者需要用 C++ 语言编写 RD 、 GR 、 BL 三个函数,每个函数都不能超过 140 个字符。每个函数都会接到 i 和 j 两个整型参数(0 ≤ i, j ≤ 1023),然后需要返回一个 0 到 255 之间的整数,表示位于 (i, j) 的像素点的颜色值。举个例子,如果 RD(0, 0) 和 GR(0, 0) 返回的都是 0 ,但 BL(0, 0) 返回的是 255 ,那么图像的最左上角那个像素就是蓝色。参赛者编写的代码会被插进下面这段程序当中(我做了一些细微的改动),最终会生成一个大小为 1024×1024 的图片。 // NOTE: compile with g++ […]

Mathematics

高度对称的多面体和它们的对偶多面体

正四面体、正方体、正八面体、正十二面体、正二十面体,这是古希腊人就发现的五种正多面体,它们拥有最高标准的对称性。这五种正多面体又叫做 Platonic 体,它们在古希腊的哲学观念中占据着至关重要的地位。 Leonhard Euler 发现,多面体的顶点数 V 、棱数 E 和面数 F 一定满足公式 V – E + F = 2 ,这叫做 Euler 多面体公式。利用这个公式,我们可以证明正多面体只有五种。假设一个正多面体的每个面都是正 p 边形,那么所有 F 个面一共就有 p · F 条边;每两条边拼在一起形成了一条棱,因而总的棱数就是 E = p · F / 2 。反过来, F 就应该等于 2 · E / p 。不妨再假设每个顶点处都汇集了 q 条棱,那么总的棱数似乎应有 q · V 个;但这样计算的话,每条棱都被重复算了两次,因而总的棱数实际上应该是 E = q […]

Mathematics

捡石子游戏、 Wythoff 数表和一切的 Fibonacci 数列

让我们来玩一个游戏。把某个国际象棋棋子放在棋盘上,两人遵循棋子的走法,轮流移动棋子,但只能将棋子往左方、下方或者左下方移动。谁先将棋子移动到棋盘的最左下角,谁就获胜。如果把棋子放在如图所示的位置,那么你愿意先走还是后走?显然,答案与我们放的是什么棋子有关。 这个游戏对于兵来说是没有意义的。在如图所示的地方放马或者放象,不管怎样都无法把它移动到棋盘的最左下角,所以我们也就不分析了。因此,我们只需要研究王、后、车三种情况。 在国际象棋中,车每次可以横着或竖着走任意多格。在上述游戏中,受到规则的限制,车每次只能向左或者向下走任意多格。如果问题中的棋子是车,答案就非常简单了:你应该选择先走。你应该直接把车移到棋盘对角线上的位置(如左图所示),然后不管对方怎么走,你都把它移回到棋盘的对角线上。这样,你就能保证必胜了。 在国际象棋中,王每次可以横着、竖着或者斜着走一格。在上述游戏中,受到规则的限制,王每次只能向左、向下或者向左下方走一格。如果问题中的棋子是王,分析出问题的答案也不算太难:你应该选择先走。你应该直接把王移到棋盘的“奇格”里(如右图所示),然后不管对方怎么走,你都可以把它再次移到某个“奇格”里。这样,你就能保证必胜了。 在国际象棋中,皇后每次可以横着、竖着或者斜着走任意多格。在上述游戏中,受到规则的限制,皇后每次只能向左、向下或者向左下方走任意多格。如果问题中的棋子是皇后,那么你应该选择先走还是后走呢?这次,问题就没那么简单了。 这个“挪动皇后”的游戏是由 Rufus Isaacs 在 1960 年左右提出来的。给定皇后在棋盘上的初始位置,如何判断出谁有必胜策略呢? Isaacs 给出了一个分析方法。 首先,第一行上的所有位置,第一列上的所有位置,以及对角线上的所有位置,都能一步直接走到棋盘的最左下角。我们可以从最左下角的位置出发,画出三条射线,把这些位置全都划掉。如果皇后位于被划掉的位置上,那么先走的人就会获胜。此时,棋盘上出现了两个死角。如果皇后在这两个地方,先走的人不得不把皇后挪到刚才被划掉的位置上,因而后走的人就必胜了。因而,从这两个地方出发,画出三条射线,被划掉的位置又是先走的人就会获胜的位置,先走的人只需要把皇后挪到这两个地方即可。此时,棋盘上又会出现两个新的死角,它们又是后走的人必胜的位置……不断这样递推下去,我们就能分析出,皇后在哪些地方时先走的人必胜,皇后在哪些地方时后走的人必胜。之前我们曾问,当皇后位于标有 × 的格子时你应该选择先走还是后走,现在我们就知道答案了:你应该后走才对。 那么,在“挪动皇后”的游戏中,哪些位置是后走的人必胜的位置呢? 画出更大的棋盘,将刚才的操作再多重复几次后,我们看见了一个非常明显的规律:这些位置大致形成了两条直线。再仔细观察,你会发现,每行每列里恰好有一个这样的位置。有没有什么公式不用递推就能找出这些位置呢?它们为什么会形成这么两条直线呢?为什么每行每列里有且仅有一个这样的位置呢?看来,这里面还有很深的水。   令 Isaacs 万万没有想到的是,这个游戏虽然是他发明的,但由此引申的问题却已经被前人解决了。 1907 年,荷兰数学家 Willem Abraham Wythoff 提出了一个双人对弈游戏,后来人们把它叫作 Wythoff 游戏。游戏规则是这样的。地上有两堆石子,其中一堆有 m 个石子,另外一堆有 n 个石子。两名玩家轮流取走石子,规定每次要么从其中一堆石子中取走任意多个石子,要么从两堆石子中取走相同数量的石子。等到谁没有石子可取了,谁就输了。也就是说,取到最后一个石子的玩家获胜。 Martin Gardner 认为, Wythoff 本人甚至也不是这个游戏最早的发明者——其实中国很早就有了这个游戏,人们把它叫作“捡石子”。 容易看出, Wythoff 游戏和“挪动皇后”是完全等价的。把棋盘从下到上各行依次标为 0, 1, 2, 3, …,把棋盘从左到右各列依次标为 0, 1, 2, 3, …,那么皇后移动时坐标变化的规则,正好与 Wythoff 游戏中两堆石子数量变化的规则是相同的。而两个游戏的目标也是相同的:谁先将游戏状态变为 (0, […]

Mathematics

实数、超实数和博弈游戏:数学的结构之美

(一)一个博弈游戏 让我们来玩一个游戏。下面有五行石子,白色的石子都是我的,黑色的石子都是你的。我们轮流拿走一个自己的石子,并且规定如果一个石子被拿走了,它后面的所有石子都要被扔掉。谁先没有拿的了,谁就输了。 ○●●○●●○●●○ ●○○●○●●○● ○○○○ ●●●○●●● ● 比如说,如果你先走的话,你可以把第四行的第三个石子拿走,按规定第四行将会只剩下前面两个石子: ○●●○●●○●●○ ●○○●○●●○● ○○○○ ●● ● 现在轮到我走了。我可以拿走第二行倒数第二个石子,于是整个棋局变成了这样: ○●●○●●○●●○ ●○○●○●● ○○○○ ●● ● 现在,假如说你拿走了第二行中的第一个石子(于是第二行就没了),那么我就赢定了。我可以拿走第一行中的第一个石子,从而让整个棋局只剩下后面三行: ○○○○ ●● ● 这三行中有四个白石子,有三个黑石子,并且每一行都是同种石子。于是整个局面完全变成了一个拼石子个数的游戏,我只需要一个一个地拿走白色石子,你必然将会率先无路可走。受此启发,我们自然地想到了一种刻画棋局的方式:把每个白色石子记作 +1 ,把每个黑色石子记作 -1 。于是 ○○○○ + ●● + ● = 4 – 2 – 1 = 1 ,结果是一个正数,这就表明该局面下我将必胜,即使此时轮到我先走。 你会发现上面的说法很有道理。毕竟白色的石子越多,对我越有利,给我带来的效用为正;而黑色的石子会减小我获胜的希望,当然应该给它赋上一个负的值。四白三黑算出来的结果为正 1 ,直观意义就是我能以一步的优势获胜。如果棋局是这样: ○○ ●●●● 那么 ○○ + ●●●● = 2 – 4 […]