Matrix67: The Aha Moments - RSS Feed

Latest articles

16 年后重谈 P 和 NP

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

一些有趣的环面多面体

环面多面体,即亏格为 1 的多面体,直观地说就是有 1 个洞的多面体。下图中三个多面体里分别有 0 个洞、1 个洞和 2 个洞。第二个多面体就是环面多面体。最近,我在研究一些和环面多面体相关的话题,在这里和大家分享一些我的发现。 ​ 由正多边形构成的环面多面体 正四面体、正六面体、正八面体、正十二面体、正二十面体、侧面均为正方形的正棱柱、侧面均为等边三角形的正棱锥、足球或者 C60 所对应的多面体等等,都是由正多边形构成的多面体。 有没有什么环面多面体也是由正多边形构成的呢?一个容易想到的做法就是,把 8 个正方体摆成一个“口”字形。这样做是不行的。正方体拼接起来后,原来的很多面会因为共面的原因合成了更大的面。站在整个多面体的角度来讲,它的各个面就不再是正多边形了。 ​ 然而,如果我们用下面这样的方法把正方体拼接起来,就漂亮地绕开了这个问题。...

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

我正在餐桌前吃早餐。餐桌上有一张圆形的大饼,有一个方形的蛋糕,还有一个甜甜圈。我依次思考了下面三个问题。你能帮我想出它们的答案吗? 3 刀切一张圆形的大饼,最多能把它分成多少块?或者说,3 条直线最多能把一个圆盘分成多少个区域? 4 刀切一个方形的蛋糕,最多能把它分成多少块?或者说,4 个平面最多能把一个正方体分成多少个区域? 3 刀切一个甜甜圈,最多能把它分成多少块?或者说,3 个平面最多能把一个(实心的)环面分成多少个区域? 提示:上一个问题的答案总会为下一个问题提供线索。 3 刀切一张圆形的大饼,最多能把它分成多少块?或者说,3 条直线最多能把一个圆形分成多少个区域? ​ 这是一个经典的小学问题。答案是 7 块。如图所示,事实上,当直线数分别为 1, 2,...

称假币问题的变形:无假币与“天平机”

大家应该听说过 9 枚硬币的问题吧。9 枚硬币当中有 8 枚是真币,有 1 枚是假币。所有的真币重量都相同,假币的重量则稍重一些。怎样利用一架天平两次就找出哪一枚硬币是假币?方法是,先把 9 枚硬币分成三组,每组各 3 枚硬币。然后,把第一组放在天平左边,把第二组放在天平右边。如果天平向左倾斜,说明假币在第一组里;如果天平向右倾斜,说明假币在第二组里;如果天平平衡,说明假币在剩下的第三组里。现在,假币的嫌疑范围就被缩小到 3 枚硬币之中了。选择其中 2 枚硬币分放在天平左右两侧。类似地,如果天平左倾,就说明左边那枚硬币是假的;如果天平右倾,就说明右边那枚硬币是假的;如果天平平衡,就说明没放上去的那枚硬币是假的。 9 硬币问题实在是太经典了,你甚至能在人教版小学五年级下册的课本里看到它。9 硬币问题还衍生出了很多变形,其中最著名的当属...

UyHiP 趣题:能否把一个凸四边形分成若干个凹四边形

下面这个趣题出自 Using your Head is Permitted 谜题站 2016 年 10 月的题目:能否把一个凸四边形分成若干个凹四边形? 答案是否定的。我们给出一个非常漂亮的证明。在下面的文字中,我们用“优角”一词来表示一个大于 180 度小于 360 度的角。 假设某个凸四边形被分成了若干个凹四边形。容易看出,每个凹四边形的内角中都有且仅有一个优角(如果没有优角,它就不是凹四边形;如果有两个或更多的优角,就与四边形内角和为 360 度矛盾)。 现在,让我们把每个凹四边形的那个优角顶点涂成蓝色。容易看出,每个蓝色顶点只能成为一个凹四边形的一个优角顶点(否则汇聚于该点处的角度之和会超过 360 度)。这意味着,每个蓝色顶点都唯一地对应一个凹四边形。如果图中的蓝色顶点一共有...

Lissajous 曲线的动画演示

随着常数 m 和 n 的变化,参数方程 x = sin(m · t), y = sin(n · t) 将会画出一系列漂亮的曲线。法国物理学家 Jules Antoine Lissajous 曾在 1857 年研究过这类曲线,因此人们把它叫做 Lissajous 曲线。我在 reddit 上看到了一个 Lissajous 曲线的动画演示,觉得看起来确实非常爽;但那个动画里没有解释曲线的生成方法,很多细节也有让人不太满意的地方,于是决定自己制作一个。这个动画展示的是 m = 13, n = 18 时的 Lissajous 曲线。

位换记号、排列测试与状态图:杂耍中的数学

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 的成绩击败了世界排名第一的...

UyHiP 趣题:几个特殊的强正则图

下面这个趣题出自 Using your Head is Permitted 谜题站 2016 年 8 月的题目,稍有改动。 屋子里有若干个人,任意两个人都有恰好 1 个共同的朋友。这有可能吗?有可能。比方说,屋子里有 9 个人,其中 8 个人正好组成 4 对朋友,第 9 个人则和前面 8 个人都是朋友。容易验证,任意两个人都有恰好 1 个共同的朋友。我们可以用下面这个图表示此时这 9 个人之间的朋友关系,其中每个点代表一个人,如果两个人是朋友,就在他们之间连一条线。 除了上图展示的情况之外,我们还能构造出很多别的同样满足要求的情况。事实上,上述方案可以扩展到一切奇数个人的情况,比如下面这样: 现在,假设屋子里有若干个人,任意两个人都有恰好 2 个共同的朋友。这有可能吗?有可能。比方说,屋子里有...

趣题:为什么偏偏是 6 格?

无穷多个相同大小的正方形格子排成一排,向左右两边无限地延伸。每个格子里都有 0 个、 1 个或多个原子。每一次,你可以对它们做下面两种操作之一: 选择某个格子,保证该格子内至少含有 1 个原子。将该格子内的其中 1 个原子分裂为 2 个,从而使得该格子内的原子数量减 1 ,两边的邻格里的原子数量分别加 1。 选择某个格子,保证两边的邻格里均至少含有 1 个原子。从两边的邻格里各取 1 个原子聚合起来,从而使得两边的邻格里的原子数量分别减 1 ,该格子内的原子数量加 1。 初始时,某个格子里有 1 个原子。现在,你需要在若干次操作之后,让它右移 6 格。也就是说,你需要用若干次操作把下面的第一个图变成第二个图(其中,数字 1 表示该格内的原子数为 1 )。继续阅读下去之前,你不妨自己先试一试。你可以在纸上画好格子,用硬币、大米、巧克力豆等物体代替原子。...

IMO2016 趣题:Geoff 的青蛙

2016 年 IMO 的第 6 题(也就是第二天比赛的第 3 题)非常有趣,这恐怕算得上是近十年来 IMO 的所有题目中最有趣的题目之一。平面上有 n ≥ 2 条线段,每两条线段都有一个交点,并且任意三条线段都不交于同一点。 Geoff 打算在每条线段的其中一个端点处放置一只青蛙,并让每只青蛙都朝向它所在线段的另一个端点。然后, Geoff 将会拍 n – 1 次手。每次拍手时,每只青蛙都立即向前跳到它所在线段的下一个交点处(青蛙们在跳跃过程中始终不会改变方向)。 Geoff 希望巧妙地安排初始时放置青蛙的方法,使得在整个过程中,任意两只青蛙都不会同时到达某个相同的交点。这个题目有两个小问。 证明:当 n 为奇数时, Geoff 一定有办法实现他的要求。 证明:当 n 为偶数时, Geoff...

Discover, share and read the best on the web

Follow RSS Feeds, Blogs, Podcasts, Twitter searches, Facebook pages, even Email Newsletters! Get unfiltered news feeds or filter them to your liking.

Get Inoreader
Inoreader - Follow RSS Feeds, Blogs, Podcasts, Twitter searches, Facebook pages, even Email Newsletters!