2006 年,我在博客(当时还是 MSN Space)上发了 《什么是 P 问题、NP 问题和 NPC 问题》 一文。这是我高二搞信息学竞赛时随手写的一些东西,是我的博客中最早的文章之一。今天偶然发现,这篇现在看了恨不得重写一遍的“科普”竟仍然有比较大的阅读量。时间过得很快。《星际争霸》(StarCraft)出了续作,德国队 7 比 1 大胜东道主巴西,《学徒》(The Apprentice)里的那个家伙当了总统,非典之后竟然出了更大的疫情。现在已经是 2022 年了。这 16 年的时间里,我读了大学,出了书,娶了老婆,养了娃。如果现在的我写一篇同样话题的科普文章,我会写成什么样呢?正好,我的新书《神机妙算:一本关于算法的闲书》中有一些相关的内容。我从书里的不同章节中摘选了一些片段,整理加工了一下,弄出了下面这篇文章,或许能回答刚才的问题吧。...
Jun 2022
环面多面体,即亏格为 1 的多面体,直观地说就是有 1 个洞的多面体。下图中三个多面体里分别有 0 个洞、1 个洞和 2 个洞。第二个多面体就是环面多面体。最近,我在研究一些和环面多面体相关的话题,在这里和大家分享一些我的发现。 由正多边形构成的环面多面体 正四面体、正六面体、正八面体、正十二面体、正二十面体、侧面均为正方形的正棱柱、侧面均为等边三角形的正棱锥、足球或者 C60 所对应的多面体等等,都是由正多边形构成的多面体。 有没有什么环面多面体也是由正多边形构成的呢?一个容易想到的做法就是,把 8 个正方体摆成一个“口”字形。这样做是不行的。正方体拼接起来后,原来的很多面会因为共面的原因合成了更大的面。站在整个多面体的角度来讲,它的各个面就不再是正多边形了。 然而,如果我们用下面这样的方法把正方体拼接起来,就漂亮地绕开了这个问题。...
Dec 2021
我正在餐桌前吃早餐。餐桌上有一张圆形的大饼,有一个方形的蛋糕,还有一个甜甜圈。我依次思考了下面三个问题。你能帮我想出它们的答案吗? 3 刀切一张圆形的大饼,最多能把它分成多少块?或者说,3 条直线最多能把一个圆盘分成多少个区域? 4 刀切一个方形的蛋糕,最多能把它分成多少块?或者说,4 个平面最多能把一个正方体分成多少个区域? 3 刀切一个甜甜圈,最多能把它分成多少块?或者说,3 个平面最多能把一个(实心的)环面分成多少个区域? 提示:上一个问题的答案总会为下一个问题提供线索。 3 刀切一张圆形的大饼,最多能把它分成多少块?或者说,3 条直线最多能把一个圆形分成多少个区域? 这是一个经典的小学问题。答案是 7 块。如图所示,事实上,当直线数分别为 1, 2,...
Sep 2021
大家应该听说过 9 枚硬币的问题吧。9 枚硬币当中有 8 枚是真币,有 1 枚是假币。所有的真币重量都相同,假币的重量则稍重一些。怎样利用一架天平两次就找出哪一枚硬币是假币?方法是,先把 9 枚硬币分成三组,每组各 3 枚硬币。然后,把第一组放在天平左边,把第二组放在天平右边。如果天平向左倾斜,说明假币在第一组里;如果天平向右倾斜,说明假币在第二组里;如果天平平衡,说明假币在剩下的第三组里。现在,假币的嫌疑范围就被缩小到 3 枚硬币之中了。选择其中 2 枚硬币分放在天平左右两侧。类似地,如果天平左倾,就说明左边那枚硬币是假的;如果天平右倾,就说明右边那枚硬币是假的;如果天平平衡,就说明没放上去的那枚硬币是假的。 9 硬币问题实在是太经典了,你甚至能在人教版小学五年级下册的课本里看到它。9 硬币问题还衍生出了很多变形,其中最著名的当属...
Sep 2021
下面这个趣题出自 Using your Head is Permitted 谜题站 2016 年 10 月的题目:能否把一个凸四边形分成若干个凹四边形? 答案是否定的。我们给出一个非常漂亮的证明。在下面的文字中,我们用“优角”一词来表示一个大于 180 度小于 360 度的角。 假设某个凸四边形被分成了若干个凹四边形。容易看出,每个凹四边形的内角中都有且仅有一个优角(如果没有优角,它就不是凹四边形;如果有两个或更多的优角,就与四边形内角和为 360 度矛盾)。 现在,让我们把每个凹四边形的那个优角顶点涂成蓝色。容易看出,每个蓝色顶点只能成为一个凹四边形的一个优角顶点(否则汇聚于该点处的角度之和会超过 360 度)。这意味着,每个蓝色顶点都唯一地对应一个凹四边形。如果图中的蓝色顶点一共有...
Sep 2021
随着常数 m 和 n 的变化,参数方程 x = sin(m · t), y = sin(n · t) 将会画出一系列漂亮的曲线。法国物理学家 Jules Antoine Lissajous 曾在 1857 年研究过这类曲线,因此人们把它叫做 Lissajous 曲线。我在 reddit 上看到了一个 Lissajous 曲线的动画演示,觉得看起来确实非常爽;但那个动画里没有解释曲线的生成方法,很多细节也有让人不太满意的地方,于是决定自己制作一个。这个动画展示的是 m = 13, n = 18 时的 Lissajous 曲线。
Oct 2016
2016 年 7 月 30 日至 8 月 7 日,第 39 届欧洲杂耍大会(European Juggling Convention)在荷兰的阿尔梅勒举行, 8 月 3 日凌晨的搏击之夜(Fight Night)自然再度成为了众人关注的焦点——它是杂耍斗(combat juggling)这项运动最大的赛事。在杂耍斗的圈子里,有两个响当当的大名你必须要知道:德国选手 Jochen Pfeiffer 目前世界排名第二,之前拿过 6 次搏击之夜的冠军;英国选手 Luke Burrage 目前世界排名第一,之前拿过 8 次搏击之夜的冠军。这一年的比赛中,两位老将均以完胜的成绩轻松进入 32 强,并在淘汰赛阶段过关斩将,最终成功在决赛场上相遇。最终,世界排名第二的 Jochen 以 5 比 4 的成绩击败了世界排名第一的...
Oct 2016
下面这个趣题出自 Using your Head is Permitted 谜题站 2016 年 8 月的题目,稍有改动。 屋子里有若干个人,任意两个人都有恰好 1 个共同的朋友。这有可能吗?有可能。比方说,屋子里有 9 个人,其中 8 个人正好组成 4 对朋友,第 9 个人则和前面 8 个人都是朋友。容易验证,任意两个人都有恰好 1 个共同的朋友。我们可以用下面这个图表示此时这 9 个人之间的朋友关系,其中每个点代表一个人,如果两个人是朋友,就在他们之间连一条线。 除了上图展示的情况之外,我们还能构造出很多别的同样满足要求的情况。事实上,上述方案可以扩展到一切奇数个人的情况,比如下面这样: 现在,假设屋子里有若干个人,任意两个人都有恰好 2 个共同的朋友。这有可能吗?有可能。比方说,屋子里有...
Sep 2016
无穷多个相同大小的正方形格子排成一排,向左右两边无限地延伸。每个格子里都有 0 个、 1 个或多个原子。每一次,你可以对它们做下面两种操作之一: 选择某个格子,保证该格子内至少含有 1 个原子。将该格子内的其中 1 个原子分裂为 2 个,从而使得该格子内的原子数量减 1 ,两边的邻格里的原子数量分别加 1。 选择某个格子,保证两边的邻格里均至少含有 1 个原子。从两边的邻格里各取 1 个原子聚合起来,从而使得两边的邻格里的原子数量分别减 1 ,该格子内的原子数量加 1。 初始时,某个格子里有 1 个原子。现在,你需要在若干次操作之后,让它右移 6 格。也就是说,你需要用若干次操作把下面的第一个图变成第二个图(其中,数字 1 表示该格内的原子数为 1 )。继续阅读下去之前,你不妨自己先试一试。你可以在纸上画好格子,用硬币、大米、巧克力豆等物体代替原子。...
Sep 2016
2016 年 IMO 的第 6 题(也就是第二天比赛的第 3 题)非常有趣,这恐怕算得上是近十年来 IMO 的所有题目中最有趣的题目之一。平面上有 n ≥ 2 条线段,每两条线段都有一个交点,并且任意三条线段都不交于同一点。 Geoff 打算在每条线段的其中一个端点处放置一只青蛙,并让每只青蛙都朝向它所在线段的另一个端点。然后, Geoff 将会拍 n – 1 次手。每次拍手时,每只青蛙都立即向前跳到它所在线段的下一个交点处(青蛙们在跳跃过程中始终不会改变方向)。 Geoff 希望巧妙地安排初始时放置青蛙的方法,使得在整个过程中,任意两只青蛙都不会同时到达某个相同的交点。这个题目有两个小问。 证明:当 n 为奇数时, Geoff 一定有办法实现他的要求。 证明:当 n 为偶数时, Geoff...
Aug 2016
Follow RSS Feeds, Blogs, Podcasts, Twitter searches, Facebook pages, even Email Newsletters! Get unfiltered news feeds or filter them to your liking.
Get Inoreader