复原小时候见过的数学魔术

今年我为北京世纪坛的数学益智游戏展贡献了不少内容。我打算在这里记录一些自己的创作、发现、收获和心得。顺便结合一下这几年的经历。这是该系列的第一篇。

有一个经典的数学小魔术。把 0 到 63 之间的数写在 6 张纸条上,其中第 1 张纸条上写着二进制表达中右起第 1 位数字为 1 的数,第 2 张纸条上写着二进制表达中右起第 2 位数字为 1 的数,第 3 张纸条上写着二进制表达中右起第 3 位数字为 1 的数,等等。给人展示 6 张纸条,问他“你的年龄出现在了哪些纸条里”。对方给出的答案就相当于告诉了你,他的年龄的二进制表达中各个地方是 0 还是 1。你就能报出他的年龄了。

今年的展会有一个主题就是过年。我们打算设计一个类似的小魔术,只不过把年龄改成生肖。由于生肖有 12 个,因此 4 张纸条就可以做到这一点。

Read more…

每个面都是凹多边形的多面体

昨晚做梦,梦见了一个有趣的数学问题:有没有什么多面体,它的每个面都是凹多边形?有趣的是,接下来我梦见自己醒了过来,然后立即上网寻找答案。我梦见我查到了相关的论文,论文作者的名字中出现了很多奇怪的符号。我梦见我开始研究论文作者的名字该怎么发音。我梦见我研究了半天没有进展,于是踏上了拜访作者本人的路……

然后就彻底醒了。然后立即上网寻找答案。废话不多说了。Branko Grünbaum 和 G. C. Shephard 在 1998 年的论文《Isohedra with Nonconvex Faces》中给出了一些例子。下图是我很喜欢的一个例子。整个多面体由12个全等的凹多边形组成。

16 年后重谈 P 和 NP

2006 年,我在博客(当时还是 MSN Space)上发了 《什么是 P 问题、NP 问题和 NPC 问题》 一文。这是我高二搞信息学竞赛时随手写的一些东西,是我的博客中最早的文章之一。今天偶然发现,这篇现在看了恨不得重写一遍的“科普”竟仍然有比较大的阅读量。时间过得很快。《星际争霸》(StarCraft)出了续作,德国队 7 比 1 大胜东道主巴西,《学徒》(The Apprentice)里的那个家伙当了总统,非典之后竟然出了更大的疫情。现在已经是 2022 年了。这 16 年的时间里,我读了大学,出了书,娶了老婆,养了娃。如果现在的我写一篇同样话题的科普文章,我会写成什么样呢?正好,我的新书《神机妙算:一本关于算法的闲书》中有一些相关的内容。我从书里的不同章节中摘选了一些片段,整理加工了一下,弄出了下面这篇文章,或许能回答刚才的问题吧。

Read more…

趣题:切完大饼和蛋糕,让我们切一切甜甜圈

我正在餐桌前吃早餐。餐桌上有一张圆形的大饼,有一个方形的蛋糕,还有一个甜甜圈。我依次思考了下面三个问题。你能帮我想出它们的答案吗?

  • 3 刀切一张圆形的大饼,最多能把它分成多少块?或者说,3 条直线最多能把一个圆盘分成多少个区域?
  • 4 刀切一个方形的蛋糕,最多能把它分成多少块?或者说,4 个平面最多能把一个正方体分成多少个区域?
  • 3 刀切一个甜甜圈,最多能把它分成多少块?或者说,3 个平面最多能把一个(实心的)环面分成多少个区域?

提示:上一个问题的答案总会为下一个问题提供线索。

Read more…