趣题:怎样向别人证明两个图不同构?

若干个顶点(vertex)以及某些顶点对之间的边(edge)就构成了一个图(graph)。如果图 G 和图 H 的顶点数相同,并且它们的顶点之间存在着某种对应关系,使得图 G 中的两个顶点之间有边,当且仅当图 H 中的两个对应顶点之间有边,我们就说图 G 和图 H 是同构的(isomorphism)。直观地说,两个图是同构的,意思就是它们本质上是同一个图,虽然具体的画法可能不一样。下面的两个图就是同构的。其中一种顶点对应关系是: 1 – a, 2 – c, 3 – d, 4 – b, 5 – e, 6 – g, 7 – h, 8 – f 。

目前,人们还没有找到任何高效的算法,能迅速判断出两个图是否同构。在普通计算机上,判断两个图是否同构,这需要花费大量的时间。因此,人们经常以图的同构为例,来解释复杂度理论和现代密码学中的诸多概念。

假设你家里的计算机十分强大,能很快判断出两个图是否同构,还能在两个图确实同构的情况下,给出一种顶点对应关系。但你的同桌家里的计算机却非常弱,没法做什么大型运算。课堂上,老师向全班展示了两个很复杂的图,不妨把它们叫作图 G 和图 H 。老师布置了一个特别的选做题:判断出这两个图是否同构。每个同学都可以提交答案,答案里只需要写“是”或者“不是”即可。按时提交答案并答对者,期末考试会获得 5 分加分;按时提交答案但答错了的,期末考试成绩将会倒扣 30 分;不参与此活动的同学,期末考试既不加分也不扣分。显然,每个同学都不敢随意提交答案,除非百分之百地能保证自己获得的答案是正确的。回到家后,借助家里的超级计算机,你很快判断出了这两个图是同构的。你给你的同桌发送了信息:“我已经算出来了,这两个图是同构的。”但是,你的同桌却回复说:“你不会是骗我的吧?”你打算怎样说服他,这两个图确实是同构的呢?

Read more…

怎样把一个立方体分成 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…

趣题:正方形能被画成什么样?

房间的正中间悬浮着一个正方形的金属框。五位画家看到这般奇迹后,立即拿出纸和笔,把这个金属框的样子画了下来。但是,由于五位画家观察这个金属框的角度不同,它们画出来的结果也互不相同。请问,这五位画家画出来的结果都是对的吗?换句话说,有没有哪一幅图或者哪几幅图根本不可能是一个正方形的透视图?

Read more…

Sierpiński 的初等数论问题

波兰数学家 Wacław Sierpiński 对数论有很多研究。在他一生出版的 50 多本书里, 250 Problems of Elementary Number Theory 一书显得格外有趣。这里面不但有各种出人意料的数学事实,还有很多精妙的证明和大胆的构造,让人大呼过瘾。我从中选择了一些问题,在这里和大家一块儿分享。下面的文字没有完全照搬书中的内容,而是做了大量的改动和扩展;若有出错的地方,还请大家指正。个别题目会涉及一些初等数论中的著名定理,它们都可以在这篇文章里找到。

Read more…