[趣题分享]从现实的油价问题到一个燃料枯竭问题。

elimqiu

假定有一天，某国某城发生汽油致命短缺。其第108号环城公路供油系统由 n ( > 0) 个加油站组成。现已知道，这些加油站的汽油的总和恰恰够且仅够一辆最省油的汽车绕该环城公路一圈，而各加油站都有这种汽车一辆，油箱皆空。为了作供油系统的最后关闭交接工作，需要某人驾车绕行公路一周完成该项任务。
试证明，在这 n 个加油站中必有某加油站的人可以完成任务：加上本站的油，驾车访问环路上的每个加油站，有油就加（假定不存在无法携带加油站所剩汽油的问题），如此继续，直到按环路返回。

elimqiu

这个问题的难度在于加油站未必是均匀分布的，加油站所剩的油的分布也未必有什么规律。

elimqiu

这题可以用数学归纳法证。[br][br]-=-=-=-=- 以下内容由 elimqiu 在 时添加 -=-=-=-=-
假定油站总数为n,则当n=1时...

luyuanhong

[这个贴子最后由luyuanhong在 2010/11/16 04:42pm 第 1 次编辑]

题  假定有一天，某国某城发生汽油致命短缺。其第108号环城公路供油系统由 n (n>0)
个加油站组成。现已知道，这些加油站的汽油的总和恰恰够且仅够一辆最省油的汽车绕
该环城公路一圈，而各加油站都有这种汽车一辆，油箱皆空。为了作供油系统的最后关
闭交接工作，需要某人驾车绕行公路一周完成该项任务。试证明，在这 n 个加油站中必
有某加油站的人可以完成任务：加上本站的油，驾车访问环路上的每个加油站，有油就加
（假定不存在无法携带加油站所剩汽油的问题），如此继续，直到按环路返回。

解  这题有一个很巧妙的证明方法。
    首先，设想某人任意选一个加油站作为出发点，在车中加上足够多的备份油，以保证
途中不会因缺油而停驶，然后驾驶这辆最省油的车绕行公路一周。他从每一个加油站出发
时，总是将该站的汽油全部加入到油箱中。他到达每一个加油站时，总是记录下这时车中
所剩的油量。由于各加油站的汽油总和恰恰够且仅够一辆最省油的汽车绕该环城公路一圈，
所以，他绕行一周，回到出发的加油站时，车中的油量还是与他最初加的备份油量一样多。
   在他到达各加油站时，记录下的车中所剩的油量中，必定有一个最小值。
   如果选择这个取到最小值的加油站作为出发点，那么，到达途中其他各加油站时，车中
所剩的油量，一定都不会小于这个最小值。因此，如果从这一站出发前的备份油量为 0 ，
也就是使得这个最小值为 0 ，那么，到达途中其他各加油站时，车中所剩的油量，也一定
都不会小于 0 ，可以顺利完成绕行一周。这样，就证明了本题的结论。