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…

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

大家应该听说过 9 枚硬币的问题吧。9 枚硬币当中有 8 枚是真币,有 1 枚是假币。所有的真币重量都相同,假币的重量则稍重一些。怎样利用一架天平两次就找出哪一枚硬币是假币?方法是,先把 9 枚硬币分成三组,每组各 3 枚硬币。然后,把第一组放在天平左边,把第二组放在天平右边。如果天平向左倾斜,说明假币在第一组里;如果天平向右倾斜,说明假币在第二组里;如果天平平衡,说明假币在剩下的第三组里。现在,假币的嫌疑范围就被缩小到 3 枚硬币之中了。选择其中 2 枚硬币分放在天平左右两侧。类似地,如果天平左倾,就说明左边那枚硬币是假的;如果天平右倾,就说明右边那枚硬币是假的;如果天平平衡,就说明没放上去的那枚硬币是假的。

9 硬币问题实在是太经典了,你甚至能在人教版小学五年级下册的课本里看到它。9 硬币问题还衍生出了很多变形,其中最著名的当属 12 硬币问题了:有 12 枚硬币,其中一枚是假币,但我们不知道假币是更重一些还是更轻一些;请利用一架天平三次找出哪一枚硬币是假币,并判断出它比真币更重还是更轻。12 硬币问题的经典程度恐怕不亚于 9 硬币问题。早在 20 世纪 40 年代,12 硬币问题就已经吸引了一大批数学家和数学爱好者,甚至有人建议把这个问题扔到德国去,以削弱德国人在二战中的战斗力。如果你想知道答案,可以在网上找找,应该很容易找到。我们今天就不讨论了。

今天,我们真正想聊的其实是这个问题的另外一种比较少见的变形:仍然是要在 9 枚硬币当中寻找 1 枚假币,仍然假设假币的重量要稍重一些,仍然只能使用天平两次;但是这一次,你所使用的是一种“天平机”,它不会立即告诉你现在是哪边重哪边轻,而是在你两次称完后把这两次的结果一并打印给你。这下,你就没法根据天平的反馈结果随机应变了,必须事先把每次怎么放硬币全规划好。那么,你该怎么办?在本文后面的内容中,均已知假币比真币更重,直至另有说明。

Read more…