一个“很显然”的结论

一个“很显然”的结论

编个计算机程序，把所有步数少于上一节中所计算的K＝〔S／a₁〕的可能的过桥方案都列举一遍，然后找出最快的，当然是一种方法，这理论上也是可行的，因为少于K步的方案只有有限多个，计算机程序必定能够将它们全部列举出来。只是当人数N增大时，过桥方案数会增加得很快。事实上，如果我们只考虑“每次过去两个人，然后这两个人中其中一个人回来”这类方案的数目的数量就已经远远超过N！个了，想像一下如果N＝1000的话所需要的计算量！况且还有更多数量的其他类型方案。特别是，我们是在做智力题，不是在学编程。当然你还可以说，如果人多的话，所需要的时间超过了12小时，那时天已经亮了，不再需要手电筒，大家可以直接过桥——唉！我们是在做智力题，不是在做抬杠式的脑筋急转弯——我们可以假设是在有漫长极夜的极地嘛，要不然，这桥是在一个黑暗山洞里，就像电影《指环王》中的那样……

但是如果不用列举法的话，我们有一个重要的任务要做，就是不仅要说明如何找到一个我们自以为最快的方案，而且还要证明这样的方法的确给出了一个最佳方案。

在我们的直觉当中，最快的方案必然有这样一个特征：每次过桥去彼岸的一定是两个人，然后一定只有一个人把手电筒送回此岸（当然要除去最后一次过桥的情况，那时就不需有人把手电筒送回来了）。但是为什么一定是这样的呢？为什么不可能有一个意想不到的巧妙方案，在那里有某一步居然需要一个人单独过到彼岸去，或者需要有两个人把手电筒送回此岸来？这是个看起来很显而易见但是我们不能支吾不回答的问题。

在讨论中我们经常需要说明，在某一时刻，桥的两边分别有哪些人，手电筒又在哪一边。这样的说明称为一个“局面”。当然，一个局面必须是合理的。比如说，不能够所有人都在桥的一边，而手电筒却在桥的另一边；一个人必须处在桥的某一边，而且只能处在桥的某一边。

比如说，在四个旅行者的问题里，如果某一个时刻A、B和C在此岸，而D在彼岸，手电筒也在彼岸，这就给出了一个局面（这个局面看起来有点奇怪，大概是D拿着手电筒一个人跑过桥去了，接下去除了他再拿着手电筒回来别无它法）。所有人和手电筒都在此岸，就是一个特殊的局面，叫作初始局面；而所有人和手电筒都在彼岸，也是一个特殊的局面，叫完结局面；所有其他的局面我们称为中间局面。

想像一下现在有两种局面。在两种局面中，手电筒都在桥的同一边（都在此岸或都在彼岸）；而且在第一种局面里所有在彼岸的旅行者，在第二种局面里也都在彼岸，而且有这样的旅行者，在第一种局面中他在此岸，而第二种局面中他在彼岸。那么我们就说第二种局面“优于”第一种局面。

比如说，在四个旅行者的问题里，第一种局面是A、B和C在此岸，而D在彼岸，手电筒也在彼岸；第二种局面是A和B在此岸，C和D在彼岸，手电筒也在彼岸。那么第二种局面就优于第一种局面。很显然，除了初始局面以外，所有手电筒在此岸的局面都优于初始局面；除了完结局面本身外，完结局面要优于所有手电筒在彼岸的局面。但是要注意的是，并不是任意给两个局面都能比较哪个优于哪个，比如说初始局面和完结局面，谁都不优于谁。

如果现在有两个局面，第二种局面要优于第一种局面。假设现在我已经有了一个方案，从第一种局面开始，通过符合题目要求的方法来移动旅行者（最多只能同时移动两个旅行者，手电筒必须和他们一起移动），在t分钟内能够使所有旅行者到达彼岸（也就是说转变成完结局面，或者说“解决”了这种局面），那么我们可以保证我们同样也有了一个方案，从第二种局面开始，在不多于t分钟内使它转变成完结局面。

为什么呢？

假设第一种局面的方案中的第一步是要把某个（或某两个）旅行者从此岸移动到彼岸（这时手电筒开始一定在此岸）。

（1）如果被移动的这个（或这两个）旅行者，在第二种局面里也在此岸，那么我们同样把他们从此岸移动到彼岸。这时两个局面化了同样多的时间转化成另两个局面，而且仍旧是第二种局面优于第一种局面。严格说来应该是“从第二种局面演化来的局面要优于从第一种局面演化来的局面”，不过这样也太拗口了，所以在下面我都用前面那种虽然不严格但是比较简明的方法来叙述。

（2）如果被移动的有两个旅行者，但是只有一个在第二种局面里是在此岸，那么我们把他从此岸移动到彼岸。如果这个旅行者是两个中跑得比较快的，那么这一步所化时间会比第一种局面要少；如果他是跑得比较慢的那个，那么这一步所化时间就和第一种局面一样。而且经过这一步转化后，第二种局面或者和第一种局面一样，或者仍旧优于第一种局面。

（3）如果被移动旅行者都不在此岸，那么情况要稍微复杂点。如果在第一种局面中经过这步移动后就变为完结局面，那么这意味着第二种局面中所有人早已到达彼岸，而这是不可能的，此时第二种局面中手电筒不可能在此岸。所以在第一种局面中经过这步移动后，还会有接下去的一步，把某个（或某两个）旅行者从彼岸移动到此岸。我们很容易看到，第二种局面无需任何耗费时间的移动，要优于第一种局面经过两次移动后演变得到的结果！因为经过两步移动后，第一种局面里在彼岸多出来的旅行者，在第二种局面里早已都在彼岸。

假设第一种局面的方案中的第一步是要把某个（或某两个）旅行者从彼岸移动到此岸（这时手电筒开始一定在彼岸），那么这就很简单，在第二种局面里这个（或这两个）旅行者一定也在彼岸，所以我们用相同的一步移动，花费一样的时间，把这个（或这两个）旅行者移动到此岸。这样得到的结果还是第二种局面要优于第一种局面。

于是总而言之，无论第一种局面中采取什么样的移动，我们总可以采取花费同样多的时间（甚至更少或者根本不花费时间）的移动，使得第二种局面或者变为和第一种局面相同，或者仍旧优于第一种局面。于是当第一种局面演变为完结局面时，第二种局面也一定演变为完结局面了，而花费的时间不会多于第一种局面所需的时间。

于是我们得到了很显然的结论：结论一：如果有两种局面，第二种局面优于第一种局面，那么我们总可以用少于解决第一种局面的时间来解决第二种局面。

这说明“优于”这个词的使用是合理的。