怎样把一个立方体分成 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 的方案上增加两笔,就能得到一个 n = 12 的方案……于是,其他所有的情况都被我们解决了。

Read more…

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 和 Shor 的神构造吧。为了方便起见,下面我们直接用“立方体”一词指代 n 维的广义立方体,“立方体的面”则代表 n 维立方体的 n – 1 维面。

Read more…

UyHiP 趣题:几乎所有数都能分解成若干个 3x · 4y 之和

下面这个题目来自 2015 年 7 月的 Using your Head is Permitted 。假设集合 S 是由所有形如 3x · 4y 的数构成的,其中 x 和 y 都是非负整数。因而,集合 S 是一个无穷集合,其中最小的几个元素依次为 1, 3, 4, 9, 12, 16, 27, … 。如果某个正整数 n 能表示成集合 S 中的一个或多个不重复的数之和,我们就说 n 是集合 S 的一个子集和。例如, 23 就是 S 的一个子集和,因为 23 可以表示成 3 + 4 + 16 。然而, 6 就不是 S 的一个子集和。

求证:除了有限多个正整数以外,其他所有的正整数都是集合 S 的子集和。

Read more…

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 和 Adi Shamir 举了一个非常简单的例子。假设初始时存储器里的所有 bit 全是 0 。存储器的写入操作是单向的,它只能把 0 变成 1 ,却不能把 1 变成 0 。我们可以把存储器里的每 3 个 bit 分为一组,每一组都只表达 2 个 bit 的值,其中 000 和 111 都表示 00 , 100 和 011 都表示 01 , 010 和 101 都表示 10 , 001 和 110 都表示 11 。好了,假设某一天,你想用这 3 个 bit 表示出 01 ,你就可以把这 3 个 bit 从 000 改为 100 ;假设过了几天,你想再用这 3 个 bit 表示出 10 ,你就可以把这 3 个 bit 从 100 改为 101 。事实上,容易验证,对于 {00, 01, 10, 11} 中的任意两个不同的元素 a 、 b ,我们都能找到两个 3 位 01 串,使得前者表示的是 a ,后者表示的是 b ,并且前者能仅仅通过变 0 为 1 而得到后者。因此,每组里的 bit 都能使用两遍,整个存储器也就具备了“写完还能再改一次”的功能。

不可思议的是,两次表达出 {00, 01, 10, 11} 中的元素,其信息量足足有 4 个 bit ,这却只用 3 个 bit 的空间就解决了。这乍看上去似乎有些矛盾,但仔细一想你就会发现,这并没有什么问题。在写第二遍数据的时候,我们会把第一遍数据抹掉,因此总的信息量不能按照 4 个 bit 来算。利用这种技术,我们便能在 300KB 的一次写入型存储器里写入 200 KB 的内容,再把这 200KB 的内容改写成另外 200KB 的内容。这听上去似乎是神乎其神的“黑科技”,然而原理却异常简单。

Read more…