 《三思科学》电子杂志
2002年第4期 总第10期
2002年4月1日
目 录
封面
封面故事
[异调]纽结
新闻
[春上莱茵早]走马观花CeBIT
[柯南]烧杯内外的风暴
图片新闻：沙尘暴
[柯南]简讯
求知
[韩雪涛]集合论简介
[九歌]动物的食性
[九歌]浅谈动物通讯
[Bird]华莱士线
[柯南]太空幽灵的威胁
[李淼]弦论通俗演义(十)
弦论通俗演义(十一)
[异调]过桥问题——经典智力题推
而广之五：一、问题
二、一个合理的假设
三、一个“很显然”的结论
四、更多的结论
五、过桥的模式
六、最慢两人的过桥方式
七、结论
译述
[M.Shermer]怀疑论:一种美德
[P.Gibbs]奥卡姆剃刀
[D.Adam]测量重力:惊人的GRACE
[K.Feder]史前E.T.——古代宇航员
的幻想(一)、(二)、(三)
观点
[赵南元]科学为什么可靠？
[碧声]末日传说
历史
[碧声]钞票上的英国(上)
书评
[逍遥]认识自私的基因
[柯南]新书介绍：环宇孤心、
科学进化史
辨伪
[方舟子]智商的误区
幽默
[雪村]中法长老联手制定“人工
取火法”
网络
[柯南]科普网站推荐：地球了望
台、互动生物学
版权声明·订阅与投稿须知
三思科学杂志社
本期责编 异调
下期责编 柯南
三思科学网站
©2002,All Rights Reserved.
|
 |
过桥问题
——经典智力题推而广之五
 异调
|  |
四、更多的结论
通过结论一我们立刻得到：
结论二：一定有这样一种最佳方案，在这个方案里，所有从彼岸到此岸的移动只需一个人。
如果最佳方案中有一步中需要两个人从彼岸移动到此岸，那么我们可以把这一步改为只移动比较快的那个人。在这一步后，我们花费了最多和原来相同的时间，得到的局面却优于按原先方案执行完这一步后的局面，所以剩下的解决步骤不会比原方案花费更多的时间，所以必定是个最佳方案。
现在我们知道，我们可以要求在最佳方案中，每次只回来一个人。在下面我们要得出另一个结论：
结论三：一定有这样一种符合结论二的最佳方案，在这个方案里，所有从彼岸到此岸的移动中，回来的这个人一定是当时在彼岸所有人中速度最快的。
假设在所有满足结论二的最佳方案中，都没有符合结论三的方案，也就是说，任何一个最佳方案中，总有某一步从彼岸到此岸的移动中，回来的那个人不是当时在彼岸所有人中速度最快的。那么我们在这些最佳方案中选取一个这样的“坏”步骤最晚出现的方案。假设这个步骤首先出现在第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步： Y1 ← 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-i步和第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步还符合结论七，而且所需要的时间也比原方案短，明显违反了假设，所以我们得到矛盾，也就是说，满足结论七的最佳方案是存在的。于是结论七成立。
←上一节 →下一节
|
|
