Science 版 (精华区)

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

过桥问题——经典智力题推而广之五 异调  　
六、最慢两人的过桥方式　　现在我们来考虑走得最慢和走得次慢的人是如何过桥的。
假设走得最慢的是Z，需时z；走得次慢的是Y，需时y。我们要证明：结论九：所有符合
结论八的最佳方案中，最慢两人过桥的模式必须相同，而且如果使用的都是模式二，那
么他们一定在一起过河。　　特别地，无论他们以什么模式过河，我们总可以在开始的
4步里将他们移动到彼岸。1) 假设Z以模式一过河，但是Y却以模式二过河（步骤旁为此
步所需时间）：　　　　　　　　　　……　　　　　　A Z →　　z　　　　　　　A
 ←　　a　　　　　　　……　　　　　　A B →　　b　　　　　　　A ←　　a　　
　　　　X Y →　　y　（X是另一不为A或B的旅行者，需时x）　　　　　　　B ←　　
b　　　　　　　……我们可以把X和Z对换，变成　　　　　　　　　　……　　　　　
　A X →　　x　（X是另一不为A或B的旅行者，需时x）　　　　　　　A ←　　a　　
　　　　　……　　　　　　A B →　　b　　　　　　　A ←　　a　　　　　　Z Y 
→　　z　　　　　　　B ←　　b　　　　　　　……这时修改过的方案比原先的耗时
短y-x分钟，和原先的“最佳方案”假定矛盾。2) 假设Z以模式二过河，但是Y却以模式
一过河（步骤旁为此步所需时间）：　　　　　　　　　　……　　　　　　A Y →　
　y　　　　　　　A ←　　a　　　　　　　……　　　　　　A B →　　b　　　　　
　　A ←　　a　　　　　　X Z →　　z　（X是另一不为A或B的旅行者，需时x）　　
　　　　　B ←　　b　　　　　　　……我们可以把X和Y对换，变成　　　　　　　　
　　……　　　　　　A X →　　x　（X是另一不为A或B的旅行者，需时x）　　　　　
　　A ←　　a　　　　　　　……　　　　　　A B →　　b　　　　　　　A ←　　
a　　　　　　Y Z →　　z　　　　　　　B ←　　b　　　　　　　……这时修改过的
方案比原先的耗时短y-x分钟，和原先的“最佳方案”假定矛盾。　　所以Z和Y必定用同
一模式过河。假设他们都以模式二过河，却不在一起：　　　　　　　　　　……　　
　　　　A B →　　b　　　　　　　A ←　　a　　　　　　W Y →　　y　（W是另一
不为A或B的旅行者，需时w）　　　　　　　B ←　　b　　　　　　　……　　　　　
　A B →　　b　　　　　　　A ←　　a　　　　　　X Z →　　z　（X是另一不为A或
B的旅行者，需时x）　　　　　　　B ←　　b　　　　　　　……我们可以把X和Y对换
，变成　　　　　　　　　　……　　　　　　A B →　　b　　　　　　　A ←　　a
　　　　　　W X →　　t　（t是w和x中比较大的那一个）　　　　　　　B ←　　b　
　　　　　　……　　　　　　A B →　　b　　　　　　　A ←　　a　　　　　　Y 
Z →　　z　　　　　　　B ←　　b　　　　　　　……这时修改过的方案比原先的耗
时短y-t分钟（Y是跑得次慢的，所以y比w和t都要大），和原先的“最佳方案”假定矛盾
。　　于是最慢两人过桥的模式必须相同，而且如果使用的都是模式二，那么他们一定
在一起过河。现在我们来考虑在方案的前4步就将他们移动到彼岸。这非常简单。　　如
果两人都是以模式一过河：　　　　　　　　　　……　　　　　　　　　 A Z →　　
z　　　　　　　　　　 A ←　　a　　　　　　　　　　……　　　　　　　　　 A 
Y →　　y　　　　　　　　　　 A ←　　a　　　　　　　　　　……我们可以把这几
步挪到最开始而不改变其他步骤：第1步：　　　　　　A Z →　　z第2步：　　　　　
　　A ←　　a第3步：　　　　　　A Y →　　y第4步：　　　　　　　A ←　　a　　
　　　　　　　　……　　如果两人以模式二一起过河：　　　　　　　　　　……　
　　　　　　　　 A B →　　b　　　　　　　　　　 A ←　　a　　　　　　　　　
 Y Z →　　z　　　　　　　　　　 B ←　　b　　　　　　　　　　……我们同样可
以把这几步挪到最开始而不改变其他步骤：第1步：　　　　　　A B →　　b第2步：　
　　　　　　A ←　　a第3步：　　　　　　Y Z →　　z第4步：　　　　　　　B ←
　　b　　　　　　　　　　……　　这就完全证明了结论九。 
--
心事浩茫连广宇,于无声处听惊雷

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