Science 版 (精华区)

发信人: qpcwth (独翅鸟), 信区: Science
标  题: 过桥问题4
发信站: 哈工大紫丁香 (2002年04月14日22:31:47 星期天), 站内信件

过桥问题——经典智力题推而广之五 异调  　
四、更多的结论　　通过结论一我们立刻得到：结论二：一定有这样一种最佳方案，在
这个方案里，所有从彼岸到此岸的移动只需一个人。　　如果最佳方案中有一步中需要
两个人从彼岸移动到此岸，那么我们可以把这一步改为只移动比较快的那个人。在这一
步后，我们花费了最多和原来相同的时间，得到的局面却优于按原先方案执行完这一步
后的局面，所以剩下的解决步骤不会比原方案花费更多的时间，所以必定是个最佳方案
。　　现在我们知道，我们可以要求在最佳方案中，每次只回来一个人。在下面我们要
得出另一个结论：结论三：一定有这样一种符合结论二的最佳方案，在这个方案里，所
有从彼岸到此岸的移动中，回来的这个人一定是当时在彼岸所有人中速度最快的。　　
假设在所有满足结论二的最佳方案中，都没有符合结论三的方案，也就是说，任何一个
最佳方案中，总有某一步从彼岸到此岸的移动中，回来的那个人不是当时在彼岸所有人
中速度最快的。那么我们在这些最佳方案中选取一个这样的“坏”步骤最晚出现的方案
。假设这个步骤首先出现在第n步。　　我们特别假设在这第n步中回来的这个人是B，他
的过桥所需的时间为b分钟，而当时在彼岸所有人中速度最快的是A，他的过桥所需的时
间为a分钟。现在我们开始把第n步“让B回来”改为“让A回来”。　　　　　　　　原
来的方案　　　　　　　修改后的方案　　　　　　　　　……　　　　　　　　　　
　……　　　第n步：　　　B ←　　　　　　　　　　A ←现在两种局面的唯一区别在
于，前一种是A在彼岸B在此岸，而后一种是B在彼岸A在此岸。但是前一种局面要比后一
种局面多耗时b-a分钟。　　在第n步后面接下去的移动步骤中，只要不牵涉A或B，那么
可以在原来方案中进行的移动仍旧可以在改变了的方案中进行。而第n步后第一次牵涉到
A或B的在原方案中的行动（我们假设它是第n+i步）只能是：1) 把A从彼岸移动到此岸。
此时我们在改造方案中的移动就是：把B从彼岸移动到此岸。这时局面就变成和原来的完
全一样了，上一次由于用A来换B节省的b-a分钟也在这步中耗费掉了。接下去我们使用原
方案完成其他移动。所以改造后的方案同样是个最佳方案：　　　　　　　　原来的方
案　　　　　　　修改后的方案　　　　　　　　　……　　　　　　　　　　　……
　　　第n步：　　　B ←　　　　　　　　　　A ←　　　　　　　　　……　　　　
　　　　　　　……　　第n+i步：　　　A ←　　　　　　　　　　B ←　　　　　　
　　　……　　　　　　　　　　　……省略号部分表示此部分两个方案相同。2) 把B
从此岸移动到彼岸（可能还有另一个过桥时间为c分钟的C和他一起移动）。这就比较简
单，第n+i步我们在改造后的方案中还是用A来代替B，然后局面就恢复到原来的情况，接
下去我们使用原方案完成其他移动：　　　　　　　　原来的方案　　　　　　　修改
后的方案　　　　　　　　　……　　　　　　　　　　　……　　　第n步：　　　B
 ←　　　　　　　　　　A ←　　　　　　　　　……　　　　　　　　　　　……　
　第n+i步：　B (C) →　　　　　　　　A (C) →　　　　　　　　　……　　　　　
　　　　　　……这里括号内的C表示有可能另有旅行者C同行，省略号部分表示此部分
两个方案相同。但我们发现这个移动所花费的时间一定要比原来的少：第n步修改后的方
案就已经要比原方案耗时少，而第n+i步中，如果c比a和b都大的话，修改后的方案和原
方案耗时相同；否则的话修改后的方案照样比原方案耗时少。所以我们得到了一个比“
最佳方案”还要“佳”的方案，所以这种情况其实是不会发生的。　　现在我们得到了
一个修改过的方案，它仍旧是个最佳方案。虽然我们并不能保证它是满足结论三的方案
，但是这并不是关键——关键在于它一直到第n步还是满足结论三的要求，这就和我们开
始的假设，即被选取的这个方案是“这样的步骤最晚出现的方案”矛盾。所以我们的原
先“假设在所有满足结论二的最佳方案中，都没有符合结论三的方案”是错误的。这样
我们就得到了结论三。　　在这里我要插一句题外话。上面的推理方法在数学中被称为
“变分方法”，这是最重要的数学方法中的一种，我们可以在所有的数学分支中看见它
的应用。它一般被用来证明存在一个具有某种特点的对象。首先我们选取一个使得某个
特征（或者函数）达到最大或者最小的对象，然后用反证法证明这样的对象就是我们要
找的对象：我们假设如果它不是我们要找的对象，那么我们总是还能把这个对象修改，
使得这个特征（或者函数）更大或更小，这就和原来最大或最小的假设矛盾。　　下面
我们会不断地用到这种方法来得出许多结论：一定存在某一个最佳解法，符合如此这般
的性质。一旦我们知道有一个最佳解法满足一些非常具体的性质以后，这个解法也就很
容易被具体写出来了。　　根据结论三我们立刻推出结论四：一定有这样一种符合结论
二—三的最佳方案，在这个方案里，每当出现手电筒在此岸的局面时，速度最快的那个
人总是在此岸。　　如果是初始局面，所有人都在此岸，当然没什么好说的。如果是手
电筒在此岸的中间局面，那么根据结论三，前一步有一个彼岸最快的人刚过来。如果这
个人不是所有人中最快的，那么说明最快的原来就已经在此岸了；如果这个人是所有人
中最快的，那么他刚刚过来，现在也已经在此岸了。所以结论四成立。　　如果在符合
结论四的最佳方案方案中，有一步是只有一个人B从此岸走到彼岸，我们会有什么推论？
如果在此岸另有一个A，他的速度比B快，那么A完全可以跟着B一起到彼岸去，这样就在
耗费相同时间的情况下，得到了一个优于原先局面的局面，根据结论一，这也是最佳方
案；如果B是此岸最快的，根据结论四，他也是所有人中最快的，过到彼岸后，根据结论
三，他马上一个人又要回来，这就使这两步移动毫无意义，徒费时间。所以我们得到：
结论五：一定有这样一种符合结论二—四的最佳方案，在这个方案里，所有从此岸到彼
岸的移动都需两个人。　　下面我们要给出一个不那么显然的结论。结论六：一定有这
样一种符合结论二—五的最佳方案，在这个方案里，每次从此岸到彼岸移动两人，要么
这两人里有一个是所有人中最快的那个，要么这两人到达彼岸后都再也不回来。　　上
面这个结论的意思是，在这个方案里不会出现这样的情况：有一步两个人跑到彼岸去，
但两人都不是跑得最快的，但是后来其中一个（或者两个都）又跑回此岸来。　　仍旧
使用变分法。假设在所有满足结论二—五的最佳方案中，都没有符合结论六的方案，也
就是说，其中的每个最佳方案，总都有某一步从此岸到彼岸的移动中，被移动的那两个
人没有一个是最快的，而且其中一个在后面的步骤中又回到此岸来。那么我们在这些最
佳方案中选取一个这样的步骤最晚出现的方案。假设这个步骤首先出现在第n步。　　我
们假设在这第n步中过去的两个人是Y和Z，他们过桥所需时间分别是y和z分钟，而在后面
的第n+i步中，Y又回到此岸来了。设A是走得最快的那个人，过桥所需时间为a分钟。由
结论四知道，他当时一定同Y和Z一起在此岸。　　现在我们开始修改这个方案，把第n步
“让Y和Z过去”改为“让A和Z过去”：　　　　　　　　原来的方案　　　　　　　修
改后的方案　　　　　　　　　……　　　　　　　　　　　……　　　第n步：　　Y
 Z →　　　　　　　　　　A Z →如果y＜z，那么改过的步骤消耗的时间和原来的一样
；如果z＜y，那么修改后的步骤消耗的时间还会更少。现在两种局面的唯一区别在于，
前一种是A在此岸Y在彼岸，而后一种恰好相反。而且我们看到，经过这样修改的第n步现
在符合“两人里有一个是所有人中最快的那个”这个结论六中的要求。剩下的工作就是
要理顺后面的步骤，使得修改过的方案仍旧是一个最佳方案，那时我们就用变分法推出
了矛盾，从而证明结论六。　　下面我们的技巧和前面所用过的略微不同，我们要修改
的不是一个移动而是一串移动。　　假设原来的第n+1步是“让Y1回来”，其中Y1是在彼
岸的某人，他是在彼岸最快的。我们把这第n+1步改为“让A回来”：　　　　　　　　
原来的方案　　　　　　　修改后的方案　　　　　　　　　……　　　　　　　　　
　　……　　　第n步：　　Y Z →　　　　　　　　　　A Z →　　第n+1步：　　 Y
1 ←　　　　　　　　　　　A ←这样修改后的步骤消耗的时间少于原先方案，因为Y1
必定跑得比A慢。如果Y1恰好就是Y自己（也就是说i=1），那么从这步以后修改前后两种
情况的局面又恢复成一样了。如果i≠1，也就是说Y1和Y不同，那么执行第n+1步后，原
先的局面和修改过后的局面的唯一差别在于前一种是Y1在此岸Y在彼岸，而后一种恰好相
反。我们注意到，根据结论三，Y1一定走得比Y快，更一般地，任何一个在n+1步到n+i步
之间从彼岸回此岸来的人都比Y要走得快。　　如果原先方案中从n+2步一直到n+i步里的
移动都不牵涉到Y1，那么我们只要把第n+i步的“Y回来”改成“Y1回来”，就理顺了所
有的步骤：　　　　　　　　原来的方案　　　　　　　修改后的方案　　　　　　　
　　……　　　　　　　　　　　……　　　第n步：　　Y Z →　　　　　　　　　　
A Z →　　第n+1步：　　 Y1 ←　　　　　　　　　　　A ←　　　　　　　　　……
　　　　　　　　　　　……第n+i步：　　 Y ←　　　　　　　　　　　Y1 ←修改后
的步骤消耗的时间少于原先所需的，因为Y1走得比Y快。　　如果不幸地在原先方案中的
第n+j步(j＜i)Y1又要和某个人M一起到彼岸去，而第n+j+1步是“Y2回此岸来”，那么我
们把第n+j步改为“A和M一起到彼岸”去，而把第n+k+1步改为“A回此岸来”：　　　　
　　　　原来的方案　　　　　　　修改后的方案　　　　　　　　　……　　　　　
　　　　　　……　　　第n步：　　Y Z →　　　　　　　　　　A Z →　　第n+1步
：　　 Y1 ←　　　　　　　　　　　A ←　　　　　　　　　……　　　　　　　　
　　　……　　第n+j步：　 Y1 M →　　　　　　　　　　A M →　第n+j+1步：　　
 Y2 ←　　　　　　　　　　　A ←这样修改后的步骤消耗的时间也要比原先的少，因
为A是最快的。如果Y2恰好就是Y自己（也就是说m=k+1），那么从这步以后修改前后两种
情况的局面就恢复成一样了。如果m≠k+1，也就是说Y2和Y不同，那么执行第n+k+1步后
，原先的局面和修改过后的局面的唯一差别在于前一种是Y2在此岸Y在彼岸，而后一种恰
好相反。　　这样我们有一个序列Y1，Y2，……，依次修改下去，每次修改后的步骤消
耗的时间不会多于原先所需的，经过最多[m/2]次修改，总会有一刻某个Yt和Y相同，结
束我们的这串修改。　　这样我们就得到了修改后的最佳方案，它的第n步也是符合结论
六的要求的。所以和我们的反证假设矛盾，和结论三的证明方式相同，我们证明了结论
六。　　在本节的结尾我们给出一个不那么显然的结论三的加强版。结论七：一定有这
样一种符合结论二—六的最佳方案，在这个方案里，所有从彼岸到此岸的移动中，回来
的这个人一定是当时在彼岸所有人中速度最快的，而且他只能是所有人中最快的或者次
快的。　　换句话说，所有返回此岸的任务都可以只由跑得最快和跑得次快的人来担当
，所有其他人一旦到达彼岸，就留在那里，再也不回来。　　我们还是使用变分法。假
设结论七是错的，所有（满足结论二—六的）最佳方案中，都必须至少有一次需要一个
跑得不是最快或次快的人回来，那么我们选取一个这样的事情发生得最晚的最佳方案。
假设在第n步，有一个C从彼岸跑回了此岸，但他不是跑得最快或次快的人。　　我们假
设A是跑得最快的人，他所需过桥时间为a分钟，B是跑得次快的人，他需要b分钟，而C需
要c分钟。我们有a＜b＜c。因为在第n步C从彼岸跑回了此岸，所以在那之前一定有一步
，C从此岸到达彼岸，而且根据结论六，那一步一定是A和C同行，我们假设此步为第n-i
步。又根据结论三，接下去一步是A回到此岸。在第n-i步和第n步间，没有有关于C的移
动。考虑第n-1步：根据结论五，这一步必定有两人从此岸移动到彼岸；这两人中没有A
或B，否则根据结论三，第n步回此岸来的就该是比较快的A或B；另外这两人中也没有C，
因为在在第n-i步和第n步间，C不移动。所以我们根据上面的分析可以写出方案中的有关
步骤： 　　　　　　　　　原来的方案　　　　　　　　　　……　　第n-i步：　　
　A C →　第n-i+1步：　　　　A ←　　　　　　　　　　……　　第n-1步：　　　
Y Z →　（Y和Z未知，但非A、B或C）　　　第n步：　　　　C ←　　　　　　　　　
　……因为第n-i步和第n步之间没有关于C的移动，而第n-1步时A和B一定在此岸（否则
根据结论三，第n步回此岸来的就该是比较快的A或B），所以我们可以把第n-1步和第n-
i+1步移到第n-1步前，方案仍旧可以合理进行（换句话说，第n-i和第n-i+1步的唯一作
用就是把C运送到了彼岸，但是直到第n步之前这个C并不起什么作用，所以我们可以把这
次运送搬到第n-1步前而不影响其他步骤）：　　　　　　　　修改后的方案　　　　　
　　　　　……　（原来第n-i步前的步骤）　　　　　　　　　　……　（原来处于第
n-i+1和第n步间的步骤）　　第n-3步：　　　A C →　（原来第n-i步）　　第n-2步：
　　　　A ←　（原来第n-i+1步）　　第n-1步：　　　Y Z →　（Y和Z未知，但非A、
B或C）　　　第n步：　　　　C ←　　　　　　　　　　……现在有问题的步骤都聚在
了一起，所以我们可以用B来代替C，进一步修改方案：　　　　　　　进一步修改后的
方案　　　　　　　　　　……　（原来第n-i步前的步骤）　　　　　　　　　　……
　（原来处于第n-i+1和第n步间的步骤）　　第n-3步：　　　A B →　　　第n-2步：
　　　　A ←　　　第n-1步：　　　Y Z →　（Y和Z未知，但非A、B或C）　　　第n步
：　　　　B ←　　　　　　　　　　……这个修改是可行的，因为根据上面的分析，
进行第n-3步前B在此岸。这样得到的方案不但直到第n步还符合结论七，而且所需要的时
间也比原方案短，明显违反了假设，所以我们得到矛盾，也就是说，满足结论七的最佳
方案是存在的。于是结论七成立。  
--
心事浩茫连广宇,于无声处听惊雷

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.229.154]