没有尽头的任务/科学美国人趣味数学集锦

作者简介

内容简介

假如你手头有个篮子，装着100只*蛋，另外还有许许多多盛放*蛋的 纸板箱。你的任务是要把所有的*蛋放进纸板箱里。每一步(每一次动作) 或者是把一只*蛋放进纸板箱，或者是把一只*蛋从纸板箱里拿出来重新 放回篮子里。规则是：接连两次把*蛋放进纸板箱之后，就必须从纸板箱 里取出一只*蛋，重新放回到篮子里。尽管这种方法效率极低，荒谬透顶 ，但显然，*后所有的*蛋都能装进纸板箱里去。 现在假定篮子里可以盛放任意多个有限数的*蛋。如果一开始你要了 许许多多*蛋，那么完成这个任务就将变得十分艰巨。不过，*初的*蛋 数一旦确定下来，完成这个任务的所需步数也就有了一个有限数的确定上 限。 如果规则允许你在任何时候都可以把任意数目的*蛋放回篮子里，情 况就会发生根本的变化。这时，完成这一任务所需的步数就不再有一个上 限，甚至开始时篮子里只有两个*蛋，也是如此。所以，把有限数的*蛋 进行装箱的任务将会按照规则的不同，或必定可以完成，或没完没了。也 可以由你选择，使这个任务在有限步数内完成，或无限地进行下去。 我们现在来考虑几个有趣的数学游戏，它们有以下特点。从直观上看 ，你似乎能够把完成任务之*永远地拖延下去，但实际上在有限多步之后 任务必然完成，这个结局无法避免。 我们的**个例子是从哲学家兼作家和逻辑学家斯穆扬(Raymond M.**u11yan)的一篇文章里找来的。设想你有无穷多个打落袋用的台球，每 个球上都标有一个正整数，而且对于每一个正整数，都有无穷多个台球以 此数作其标号。你还有一只箱子，其中盛有有限多个标记着数字的台球。 你的目标是要把箱子出空。每一步要求你从箱子里取出一只台球，同时换 上任意有限多只标号比它小的台球。1号台球是**的例外，因为没有比1 *小的号码，所以对每个1号台球来说，没有台球来替换它，只能是有出无 人了。 不难用有限多步就把箱子出空。这只要把每个标号比1大的台球用一个 1号台球来替换，直到箱子里剩下来的全是1号台球，然后再每次取出一个1 号台球就行了。不过，规则允许你用任意有限数目标号较小的台球来替换 一个标号大于1的台球。譬如说，你可以取出一个标号为1000的台球，而换 上十亿个标号为999的台球，再加上一百亿个标号为998的台球，再加上一 百亿亿个标号为997的台球，再加上……。这样一来，箱子里台球的总数在 每一步都增加得超乎你的想象。试问，你是否能够永远拖延下去，使箱子 不会出空呢？实际上，箱子终有出空之*，这个结局是无法避免的，尽管 乍看起来这似乎令人难以置信。 请注意，比起*蛋游戏来，出空箱子所需的步数要庞大得多，不仅是 开始时的台球数没有限制，而且每次取出一个标号大于1的台球之后，用来 替换它的台球的数目也没有限制。借用康韦(John Horton Conway)的话来 说，这个过程乃是“无界的无界”。在此游戏的每一个阶段，只要箱子里 还有着一个标号大于1的台球，就不可能预见要把箱子里1号台球之外的台 球全部取出究竟需要多少步。(如果所有台球的标号全都是1，出空箱子的 步数当然就和1号台球的个数一样多。)不过，无论你替换台球的办法多么 高明，在经历了有限多步之后，箱子终究是会出空的。当然，我们必须假 设，尽管不一定要求你***，然而也需要你活得足够长来完成这项任 务。 斯穆扬将这个惊人结果发表在他的一篇论文《树图与台球游戏》中， 此文刊载于《纽约科学院年报》(第321卷，86—90页，1979年)上，文中给 出了好几个证明，其中有一个是用归纳法来简单论证的。斯穆扬的论述好 得无以复加，我没有本事改进，还是照用他的原话为好： 如果箱子里的台球全是标号1，那么显然我们输定了。假设箱子里台球 的标号*大是2，那么，一开始我们有着有限多个2号台球和有限多个1号台 球。我们不可能一直老是把1号球扔出去，因而迟早我们总要把其中的一个 2号球拿走。这样一来，箱子里的2号球就少了一个(不过，箱子里却可能包 含比开始时要多得多的1号台球)。现在，我们还是不能老是在把1号球扔出 去，因此迟早我们总还是要扔出另一个2号球。可以看出，经过有限多步之 后，我们必然要扔出*后一只2号台球，这时我们又回到了箱子里只有1号 台球的情形。我们已经知道，这种情形肯定是要失败的。这就证明了，当 台球的*大标号为2时，过程必将中止。那么，*大标号为3时又如何呢？ 我们不能一直不断地把标号为2的球扔出去(我们刚刚证明了这一点)，因此 我们迟早总要扔出去一个3号球。所以，到头来我们必定要扔出去*后一个 3号球。这就把问题归结到上面的、*大标号为2的情形，而这种情形我们 已经解决了。 斯穆扬还用树图作为这个游戏的模型来证明它必定终止。所谓“树” 就是指一组线段，每条线段联结两个点，而且每一个点都通过**的一串 线段联结到某一点，该点称为树的根。台球游戏的**步(用台球装箱)可 通过模型来刻画：把每只球表示为一个点，点的号码等同于球的号码，再 用一根线段通向树根。当一只球被许多只标号较低的球替换时，球上的原 有标号将被抹去，而代之以号数较大的点，然后这些点都联结到那个被移 去的球所代表的点。就这样，树图将会逐步地向上增长，而其“端点”(不 是“根”、而且只是用一根线段与别的点相联结的点)就表示在该阶段箱子 里的台球。P31-34