经典智力题推广——过桥问题(一)
爱比不爱更寂寞-
经典智力题推广——过桥问题（一）
一、问题
在漆黑的夜里，
< br>四位旅行者来到了一座狭窄而且没有护栏的桥边。
如果不借助手电筒的
话，大家是无论如何也不敢过桥去的。不幸的是，
四个人一共只带了一只手
电筒，
而桥窄得
只够让两个人同时过。如果各自单独过桥的话，
四人所需要的时间分别是
1
、
2
、
5
、
8
分钟；
而如果两人同时过桥，
所需要的时间就是走
得比较慢的那个人单独行动时所需的时间。
问题
是，如何设计一
个方案，让这四人尽快过桥。
<
/p>
假设这四人分别为
A
、
< br>B
、
C
、
D
。很明显，开始两人拿着手电筒过桥后，手电筒就在桥
的另
一边了，
此时需要已经过桥的那两人中的一个再把手电筒送回桥这边。
< br>送手电筒回来过
桥也要化时间，
所以要选一个跑得比较快
的。
一个很自然的想法就是，
每次让跑得最快的
A
陪着另一个过桥，然后
A
快
速地跑回来，再陪下一位过去，最后所有人就都可以过桥了。
让我们来算一下这要多长时间。
为了
方便起见，
我们把旅行者出发的桥的这一边称为
“
此
岸
”
，而把旅行者想要到
达的那边叫
“
彼岸
”
< br>。在表达一个过桥方案时，我们用
“←”
来表示从
彼岸到此岸的移动，用
“→”
表示从此岸到彼
岸的移动。前面
“A
护送大家过河
”<
/p>
的方案就可以
写成：
（右边数字为完成此
步骤所需时间）
A
B
→
2
A
←
1
A
C
→
5
A
←
1
A
D
→
8
一共
就是
2+1+5+1+8=17
分钟。
但其实有更快的办法：
A
B
→
2
A
←
1
C
D
→
8
B
←
2
A
B
→
2
一共是
2+1+8+2+2=15
分钟。这个办法的聪明之处在于让两个走得最慢的人同时过桥，这样
花去的时间只是走得最慢的那个人花的时间，
而走得次慢的那位就不用另花时间过桥
了。
可
以把所有可能的方案都列举一遍，就会发现这是最快的方
案了。
现在我们把这个问题推广到
N(N≥4)
个人过桥的情况：如果
有
N
个旅行者，假设他们有
各自所需的
过桥时间（正实数）
。在只有一只手电筒的情况下，要过上述的一条桥，怎样才
能找到最快的过桥方案？
假设最快地把
N
个旅行者从此岸移动到彼岸需要
f
分钟时间，
那么我们把所有在
f
分钟
时
间内把
N
个旅行者从此岸移动到彼岸的方案称为
“
最佳方案
”
。最佳方案很有
可能不止一
个，我们的目的是要找到一个最佳方案，但是并不需要把所有的最佳方案全都
找出来。
二、一个合理的假设
为了讨论的方便起见，
这一节我们要说明的是，
事实上我们可以假设每个旅行者的速度
都是不一样的。
这样当我们说一些人中
“
最快的那个
”
，
“
次慢的那一个
”
时，
都不会有歧义了，
因为每个人的速度都是独一无二的。
这个假
设在讨论中并非必要，
只是为了在证明的叙述过
程中避免不断地
啰嗦类似
“
我们让两人中最快的那个过桥，如果两人一样快，那
就随便选一
人
”
、
“
我们选在彼岸最快的那个人回来，
如果上一步刚从此岸到
彼岸的人中，其中有一个是
现在彼岸走得最快的之一，我们就特别选择让他回来
”
之类的话。
为什么我们可以假设每个旅行者的速度都是不一样的？原理就
在于，
我们可以把原来过
桥时间相同的旅行者的过桥时间分别加
上一个不同的但是非常非常小的量，
这样就能保证旅
行者的速度
是不一样的了。
但是因为加上去的量都非常小，
所以对最终总的
过桥时间的影响
也非常小。
所以这样改动过后得到的最佳方案在
原来的条件下实施的话，
也该是原来条件下
的最佳方案。
如果你对上面
的说明满意了，
就完全可以跳过这一节直接看第三节。
这一节后
面啰哩叭
嗦的都是为了向一些对严格性要求比较高的朋友解释上面所说的方法的确可行。
首先对
于任何一组
N
个旅行者，假定他们过桥所需的时间分别为
a
1
、
a
2
、
……
、
a
N
，它
们都是大于零的实
数。假设这个序列已经从小到大排列了（当然不排除其中有数相等）
。每
次都由第一个旅行者陪同一个人过桥，
然后第一个旅行者回来，
这样一个方案所需要的时间
是：
S = (N-2)*a
1
+a
2
+……+a
n
<
/p>
（第一个旅行者要返回
N-2
次）
。所以最佳方案所需要的时间一定不会比
S
大
。
我们
把一个过桥方案中让一个或者两个人拿着手电筒从桥的一边走到另一边的一次移
动叫做这
个方案中的一次移动或者
“
一步
”
，
就是前面解四个人的题中使用
“→”
或
“←”
来表示
的
一个步骤。
因为一次移动所需要的最少的时间是
a
1
分钟，
所以最佳方案中所需的移动步数
一定不会多于
K=[S/a
1
]
步，这里
是取整运算。
让我们考虑一下
所有在
K
步以内完成的方案。
上面的例
子表明这样的方案至少有一个，
而且这样的方案显然只有有限多个，假设一共有
M
个。我们又设这些方案执行时要花的时
间是<
/p>
t
1
、
t
2
、
……
、
t
M
我们还可以假设上面这些时间已经从小到大排列了，
t1
< br>就是最佳方案所需要的时间。
现在是关键的步骤。我们要选取一个很小的正实数
ε
＞
0
。它有多小呢？它
必须满足下
面的条件：
1)
对于任何两个过桥时间不同的旅行者（假设他们的过桥时间是
a
和
b
分钟）
，必须满
足
ε
＜
|a-b|/N
。换句话说，
Nε
要小于不同的旅行者过桥时间之间的
差别
。
2)
对于任何两个所需的完成时间不同的
K
步以内的方案（假设它
们的所需时间是
t
和
s
分
钟）
，必须满足
ε
＜
|t-s|/K
。换句话说，
Kε
要小于不同的方案完成时间之间的差别
。
因为旅行者的数目和方案的数目都是有限的，所以我们必然可以选取这
样一个
ε
。至于这两
个条件有什么用，
我们马上就可以看到。
假设若干个旅行者过桥的时间都是一样的
a
分钟
，
我们就把题目改一下，
使得他们的过
桥时间分别为
a
、
a+ε/N
、
a+2ε/N
、
a+3ε/N……
如果有
其他的旅行者过桥时间相互一样，
也按照同样方式修改题目。
这
时在修改后的题目中，
如果原来两个旅行者所需的过桥时间相同，
那么现在就变得不同，
差一个非常小的量
（不会
超过
ε
）
；
如果原来两个旅行者所需的过桥时间不同，
那么根据上面的条件
1)
，
现在还是不同，
而且原
来谁比较快，现在仍旧是他比较快。
我们看看这个修改后的题目的最佳方案和原来的题目的最佳方
案有什么联系。
假设我们已经有一个关于修改后的题目的最佳方案，
那么它所需要的时间必定是
这个模
样的：
a +
bε
我们知道
bε
< br>部分是修改时把旅行者过桥时间
“
微调
< br>”
了以后造成的，而且每走一步这部分的
改变不会超过<
/p>
ε
，所以我们有
0
＜
b
＜
K=[S/a1]
。
如果我们把这个最佳移动方案照搬到原来的题目中去，
所需要的时间就是
a
分钟。
这个
方案应
该同样是原来题目中的最佳方案。否则的话，假设我们有另一个方案，所需时间为
a'<
/p>
，而且
a'
＜
a
。根据上面取
ε
时候的条件
2)
，我们有
a'
＜
a +
Kε
把这个耗时
a'
的方案搬到改动过的题目里去的话，所需的时间就会是
a' + b'ε
其中
0
＜
b'
＜
K
。
所以根据
a'
＜
a+Kε
a'
+ b'ε
＜
a +
bε
这就和
a+bε
是改动后题目的最佳方案所需的时间矛盾了。
所以只要找到一个修改过的题目中的最佳方案，
我们就得到了原来题目中的一个最佳方
案，于是我们只要考虑所有旅行者的速
度都不同的题目就可以了。
三、一个
“
很显然
”
的结论
编个计算机程序，
把所有步数少于上一节中所计算的
K=[S/a
1
]
的可能的过桥方案都列举
一遍，然
后找出最快的，当然是一种方法，这理论上也是可行的，因为少于
K
步的方案只
有有限多个，计算机程序必定能够将它们全部列举出来。只是当人数
N
增大时，过桥方案
数会增加得很快。事实
上，如果我们只考虑
“
每次过去两个人，然后这两个人中其中一
个人
回来
”
这类方案的数目的数量就已
经远远超过
N!
个了，想像一下如果
N
=1000
的话所需要的
计算量！况且还有更多数量的其他类型
方案。特别是，我们是在做智力题，不是在学编程。
当然你还可以说，如果人多的话，所
需要的时间超过了
12
小时，那时天已经亮了，
不再需要
手电筒，
大家可以直接过桥
< br>——
唉！
我们是在做智力题，
不
是在做抬杠式的脑筋急转弯
——
我们可以假设是在有漫长极夜的
极地嘛，
要不然，
这桥是在一个黑暗山洞里，就象电影
《指
环王》中的那样
……
但是如果不用列举法的话，<
/p>
我们有一个重要的任务要做，
就是不仅要说明如何找到一个
我们自以为最快的方案，而且还要证明这样的方法的确给出了一个最佳方案。
< br>
在我们的直觉当中，
最快的方案必然有这样一个特征：
每次过桥去彼岸的一定是两个人，
然后一定只有一个人把手电筒送回此岸
（当然要除去最后一次过
桥的情况，
那时就不需有人
把手电筒送回来了）
。但是为什么一定是这样的呢？为什么不可能有一个意想不到的巧妙方
案，
在那里有某一步居然需要一个人单独过到彼岸去，
或者需要有两个人
把手电筒送回此岸
来？这是个看起来很显而易见但是我们不能支吾不回答的问题。
在讨论中我们
经常需要说明，
在某一时刻，
桥的两边分别有哪些人，
手电筒又在哪一边。
这样的说明称为一个
“
局面
”
。当然，一个局面必须是合理的。比
如说，不能够所有人都在桥
的一边，
而手电筒却在桥的另一边；
一个人必须处在桥的某一边，
而且只能处在桥的某一边。
比如说，在四
个旅行者的问题里，如果某一个时刻
A
、
B
和
C
在此岸，而
< br>D
在彼岸，
手电筒也在彼岸，这就给出了一个局面（这个
局面看起来有点奇怪，大概是
D
拿着手电筒
一个人跑过桥去了，
接下去除了他再拿着手电筒回来别无它法）
。
所有人和手电筒都在此岸，
就是一个特殊的局面，叫作<
/p>
初始局面
；而所有人和手电筒都在彼岸，也是一个特殊的局面，<
/p>
叫
完结局面
；所有其他的局面我们称为<
/p>
中间局面
。
想像一下现在有两种局面。
在两种局
面中，
手电筒都在桥的同一边
（都在此岸或都在彼
岸）
；而且在第一种局面里所有在彼岸的旅行者，在第二种局面里也都在彼岸
，而且有这样
的旅行者，
在第一种局面中他在此岸，
而第二种局面中他在彼岸。
那么我们就说第二种局面
“
优于
”
第一种局面。
比如说，在四个旅行
者的问题里，第一种局面是
A
、
B
和
C
在此岸，而
D
在彼岸，手
电筒也在彼岸；第二种局面是
A
和
B
在此岸，
C
和
D
在彼岸，手电筒也在彼岸。
那么第二
种局面就优于第一种局面。
很显然，
< br>除了初始局面以外，
所有手电筒在此岸的局面都优于初
始
局面；
除了完结局面本身外，
完结局面要优于所有手电筒在彼岸
的局面。
但是要注意的是，
并不是任意给两个局面都能比较哪个
优于哪个，
比如说初始局面和完结局面，
谁都不优于谁。
如果现在有两
个局面，第二种局面要优于第一种局面。假设现在我已经有了一个方案，
从第一种局面开
始，
通过符合题目要求的方法来移动旅行者
（最多只能同时移动
两个旅行者，
手电筒必须和他们一起移动）
，在
t
分钟内能够使所有旅行者到达彼岸（也就是说转变成完
结局面，或者说
“
解决
”
了这种局面）
，那么我们可以保证我们同样也有了一个方案，从第二
种局面开始，在不多于
t
分钟内使它转变成完
结局面。
为什么呢？
假设第一种局面的方案中的第一步是要把某个
（或某两个）
旅行者从此岸移动到彼岸
（这
时手电筒开始一定在此岸）
。
1)
如果被移动的这个（或这两个）旅行者，在第二种局面里
也在此岸，那么我们同样把他
们从此岸移动到彼岸。
这时两个局
面化了同样多的时间转化成另两个局面，
而且仍旧是第二
种局面
优于第一种局面。
（严格说来应该是
“
从第二种局面演化来的局面要优于从第一种局面
演化来的局面
”
，不过这样也太拗口了，所以在下面我都用前面那种虽然不严格但是比较简
明的方法来叙述。
）
2)
如果被移动的有两个旅行者，但是只有一个在第二种局面里是在此岸，那么我们把他从<
/p>
此岸移动到彼岸。
如果这个旅行者是两个中跑得比较快的，
那么这一步所化时间会比第一种
局面要少；
如
果他是跑得比较慢的那个，
那么这一步所化时间就和第一种局面一样。
< br>而且经
过这一步转化后，第二种局面或者和第一种局面一样，或者仍旧优于第一种
局面。
3)
如果被移动旅行者都不
在此岸，那么情况要稍微复杂点。如果在第一种局面中经过这步
移动后就变为完结局面，
那么这意味着第二种局面中所有人早已到达彼岸，
而这是不可能
的，
此时第二种局面中手电筒不可能在此岸。
所以在第一种局面
中经过这步移动后，
还会有接下
去的一步，把某个（或某两个）
旅行者从彼岸移动到此岸。我们很容易看到，第二种局面无
需任何耗费时间的移动，
要优于第一种局面经过两次移动后演变得到的结果！
因为经过两步<
/p>
移动后，第一种局面里在彼岸多出来的旅行者，在第二种局面里早已都在彼岸。
假设第一种局面的
方案中的第一步是要把某个
（或某两个）
旅行者从彼岸移动到此
岸
（这
时手电筒开始一定在彼岸）
，那
么这就很简单，在第二种局面里这个（或这两个）旅行者一
定也在彼岸，所以我们用相同
的一步移动，花费一样的时间，把这个（或这两个）旅行者移
动到此岸。这样得到的结果
还是第二种局面要优于第一种局面。
于是总而言之，
无论第一种局面中采
取什么样的移动，
我们总可以采取花费同样多的时
间（甚至更少
或者根本不花费时间）的移动，使得第二种局面或者变为和第一种局面相同，
或者仍旧优
于第一种局面。
于是当第一种局面演变为完结局面时，
第二种局
面也一定演变为
完结局面了，而花费的时间不会多于第一种局面所需的时间。
于是我们得到了很显然的结论：
结论
一：
如果有两种局面，
第二种局面优于第一种局面，
那么我们总可以用少于解决第一种
局面的时间来解决第二种局面。
这说明
“
优于
”
这个词的使用
是合理的。
四、更多的结论
通过结论一我们立刻得到：
结论二：
一定有这样一种最佳方案，在这个方案里，所有从彼岸到此岸的移动只需一个人。
如果最佳方案中有一步中需要两个
人从彼岸移动到此岸，
那么我们可以把这一步改为只
移动比较快
的那个人。
在这一步后，
我们花费了最多和原来相同的时间，<
/p>
得到的局面却优于
按原先方案执行完这一步后的局面，
所以剩下的解决步骤不会比原方案花费更多的时间，
所
以必定是个最佳方案。
现在我们知道，
我们可以要求在最佳方案中，
每次只回来一个人。
在下面我们要得出另
一个结论：
结论三：
一定有这样一种符合结论二的最佳方
案，
在这个方案里，
所有从彼岸到此岸的移动
< br>中，回来的这个人一定是当时在彼岸所有人中速度最快的。
假设在所有满足结论二的最佳方案
中，
都没有符合结论三的方案，
也就是说，
任何一个
最佳方案中，
总有某一步从彼岸到此岸的移动中，
回来的那个人不是当时在彼岸所有人中速
度最快的。
那么我们在这些最佳方案中选取一个这样的
“
坏<
/p>
”
步骤最晚出现的方案。
假设这个
步骤首先出现在第
n
步。
我们特别假设在这第
n
步中回来的这个人是
B
，
他的过桥所需的时间为
b
分钟，
而当时
在彼岸所有人中速度最快的是
A
，
他的过桥所需的时间为
a
分钟。
现在我们开始把第
n
步
“
让
B
回
来
”
改为
“
让
A
回来
”
。<
/p>
原来的方案
修改后的方案
……
……
第
n
步：
B ←
A ←
现
在两种局面的唯一区别在于，
前一种是
A
在彼岸
B
在此岸，而后一种是
B
在彼岸
A
在此
岸。
但是前一种局面要比后一种局面多耗时
b-a
分钟。
在第
n
步后面接下去的移动步骤中，只要不牵涉
A
或
B
，那么可以在原来方案中进行
的移动仍旧可以在改变了的方案中进行。而第
n
步
后第一次牵涉到
A
或
B
的在原方案中的
行动（我们假设它是第
n+i
步）只能是：
1)
把
A
从彼岸移动到此岸。此时我们在改造方案中的移动就是：把
B
从彼岸移动到此岸。
这时局面就变成
和原来的完全一样了，上一次由于用
A
来换
B
节省的
b-a
分钟也在这步中<
/p>
耗费掉了。接下去我们使用原方案完成其他移动。所以改造后的方案同样是个最佳方案：<
/p>
原来的方案
修改后的方案
……
……
第
n
步：
B ←
A ←
……
……
第
n+i
步：
A ←
B ←
……
……
省略号部分表示此部分两个方案相同。
2)
把
B
从
此岸移动到彼岸（可能还有另一个过桥时间为
c
分钟的
C
和他一起移动）
。这就
比较简单，
第
n+i
步我们在改造后
的方案中还是用
A
来代替
B
，
然后局面就恢复到原来的情
况，接下去我们使用
原方案完成其他移动：
原来的方案
修改后的方案
……
……
第
n
步：
B ←
A ←
……
……
第
n+i
步：
B (C) →
A (C)
→
……
……
<
/p>
这里括号内的
C
表示有可能另有旅行者<
/p>
C
同行，省略号部分表示此部分两个方案相同。但
我们发现这个移动所花费的时间一定要比原来的少：
第
n
步修改后的方案就已经要比原方案
耗时少，而第
n+i
步中，如果
c
比
a
和
b
都大的话，
修改后的方案和原方案耗时相同；否则
的话修改后的方案照样比原方案耗时少。所以我们
得到了一个比
“
最佳方案
”
还要
“
佳
”
的方
案，所以这种情况其实是不会发生的。
现在我们得到了一个修改过的方案
，
它仍旧是个最佳方案。
虽然我们并不能保证它是满
足结论三的方案，但是这并不是关键
——
关键在于
它一直到第
n
步还是满足结论三的要求，
这就和我们开始的假设，
即被选取的这个方案是
“
这样的步骤最晚出现的方案
”
矛盾。
所以我
们的原先
“
假设在所
有满足结论二的最佳方案中，
都没有符合结论三的方案
”
是错误的。
这样
我们就得到了结论三。
在这里我要插
一句题外话。
上面的推理方法在数学中被称为
“
变分方法
”
，
这是最重要的<
/p>
数学方法中的一种，
我们可以在所有的数学分支中看见它的应用。
它一般被用来证明存在一
个具有某种特点的对象。
首先我们选取一个使得某个特征
（或者函数）
达到最
大或者最小的
对象，
然后用反证法证明这样的对象就是我们要找
的对象：
我们假设如果它不是我们要找的
对象，那么我们总是还
能把这个对象修改，使得这个特征（或者函数）更大或更小，这就和
原来最大或最小的假
设矛盾。
下面我们会不断地用到这种方法来得出许多结论：
一定存在某一个最佳解法，
符合如此
这般的性质。
一旦我们知道有一个最佳
解法满足一些非常具体的性质以后，
这个解法也就很
容易被具体
写出来了。
根据结论三我们立刻推出
结论四：<
/p>
一定有这样一种符合结论二
—
三的最佳方
案，
在这个方案里，
每当出现手电筒在此
岸的局面时，速度最快的那个人总是在此岸。
如果是初始局面，
所有人都在此岸，
当然没什么好说的。
如果是手电筒在此岸的中间局
面，
那么根据结论三，
前一步有一个彼岸最快的人刚
过来。
如果这个人不是所有人中最快的，
那么说明最快的原来就
已经在此岸了；
如果这个人是所有人中最快的，
那么他刚刚过来
，
现
在也已经在此岸了。所以结论四成立。
如果在符合结论四的最佳方
案方案中，有一步是只有一个人
B
从此岸走到彼岸，我们
会有什么推论？如果在此岸另有一个
A
，他的
速度比
B
快，那么
A
< br>完全可以跟着
B
一起到
彼岸去，
这样就在耗费相同时间的情况下，得到了一个优于原先局面的局面，根据结论一，
这也是
最佳方案；如果
B
是此岸最快的，根据结论四，他也是所有人中
最快的，过到彼岸
后，根据结论三，他马上一个人又要回来，这就使这两步移动毫无意义
，徒费时间。所以我
们得到：
结论五
：
一定有这样一种符合结论二
—
四的最
佳方案，
在这个方案里，
所有从此岸到彼岸的
< br>移动都需两个人。
下面我们要给出一个不那么显然的结论。
结论六：
一定有这样一种符合结论二
—
五的最佳方案，
在这个方案里，
每次从此岸到彼岸移
动两人，
要么这两人里有一个是所有人中最快的那个，
要么这两人到达彼岸后都再也不回来。
上面这个结论的意思是，
在这个方案
里不会出现这样的情况：
有一步两个人跑到彼岸去，
但两人都不
是跑得最快的，但是后来其中一个（或者两个都）又跑回此岸来。
仍旧使用变分法。
假设在所有满足结论二
—
五的最佳方案中，
都没有符合结论六的方案，
也就是说，
其中的每个
最佳方案，
总都有某一步从此岸到彼岸的移动中，
被移动的那两
个人
没有一个是最快的，
而且其中一个在后面的步骤中又回到此
岸来。
那么我们在这些最佳方案
中选取一个这样的步骤最晚出现
的方案。假设这个步骤首先出现在第
n
步。
我们假设在这第
n
步中过去的两个人是
Y
和
Z
，他们过桥所需时间分别是
y
和
z
分钟，
而在后
面的第
n+i
步中，
Y
又回到此岸来了。设
A
是走得最快的那个人，过桥所需
时间为
a
分钟。由结论四知道，他当时一定同
< br>Y
和
Z
一起在此岸。
现在我们开始修改
这个方案，把第
n
步
“
让
Y
和
Z
过去
”
改为
“
让
A
和
Z
过去
”
：
原来的方案
修改后的方案
……
……