一类相似的智力题–加油问题

http://wirelessyang.info/2009/04/%E4%B8%80%E7%B1%BB%E7%9B%B8%E4%BC%BC%E7%9A%84%E6%99%BA%E5%8A%9B%E9%A2%98-%E5%8A%A0%E6%B2%B9%E9%97%AE%E9%A2%98/

相信每个人都会对这4个问题有直观的解答，但是最关键的问题在于如何证明某个解答是最优的

1猴子搬香蕉问题wirelessyang.info

一个小猴子边上有100根香蕉，它要走过50米才能到家，每次它最多搬50根香蕉，（多了就被压死了），它每走1米就要吃掉一根，请问它最多能把多少根香蕉搬到家里。

逻辑推理：

a)  小猴子需要搬运n次，之前n次需要储存一些香蕉在半路，否则达不到最优。

b) 小猴子每次开始搬运的时候需要搬50根，否则达不到最优。（也就是搬运两次）

c) 小猴子第一次搬运不可能超过25m。wirelessyang.info

d) 小猴子第一次搬运到50*(1/3)m时可留下 50*(1/3)根香蕉做储存。

e) 小猴子把香蕉放在0～50*(1/3)m处无法取得最优；小猴子把香蕉放在50*(1/3)～25m处无法取得最优。（也就是说只能放在50*(1/3)m处） 假设小猴子能在 50*(1/3)m处存放x根香蕉，则 50=3x，x=16.666…

因为x必须是整数，所以小猴子能在 16m处存放18根香蕉。 因此最后一次搬运的时候能把16根香蕉搬运到家里。

2飞机加油问题wirelessyang.info

(据说是微软面试题)

已知：每个飞机只有一个油箱， 飞机之间可以相互加油（注意是相互，没有加油机） 一箱油可供一架飞机绕地球飞半圈， 问题：为使至少一架飞机绕地球一圈回到起飞时的飞机场，至少需要出动几架飞机？（所有飞机从同一机场起飞，而且必须安全返回机场，不允许中途降落，中间没有飞机场）。 wirelessyang.info

拿到本题后,直觉得出来的答案是Fig1(b),而正确的答案是Fig1(a),但网上大多没给出关于最优解的证明。

（提供一个类似的理论分析：PDF 来源：chen’s blog）

在这里诚心请教用逻辑分析证明Fig1(a)最优的方法：请联系我

3 汽车加油问题1wirelessyang.info

一条公路1000公里，一辆汽车加满一次油 需要500单位的油 可以行驶500公里，请问从公路这头行驶到另一头至少一共需要多少单位的油？假设公路边任意位置点都有加油筒（筒初始为空），可以将车中油暂存到路边的加油筒中。

出乎我意料的是，这道题居然要用Backward Induction的方法，看似和前面几道题十分类似，但是解题思路却完全不一样。由反向归纳的思想进行分析的步骤如下： 首先确定一个原则，为了尽量省油，我们就要让车在路上的行程尽量短，不做过多的折回。直观上可以判断：越靠近起点的路经过的折回越多，越靠近终点的路经过的折回越少。因此至少要多少油料的问题就转化成了如何使车在路上折回的次数越少的问题。从终点向起点看去，折回的次数从0严格递增。

a)从终点向起点看去，最优的策略是车直接到达（也就是不折回），而这样需要在离终点500公里的地方（暂且叫作中专点1）放500单位油

b)从离终点500公里的地方向起点看去，最优的策略是从某一点（暂且叫作中转点2）折回1次到达（次数是1因为折回次数总是严格递增，我们需要让递增速度最慢）。我们的目标是让中转点2离中转点1尽可能得远，同时能够保证能成功地通过折回一次来给中转点1提供500单位油。根据引理1，中转点2需要离中转点1 (500/3)公里，同时需要在中转点2放置1000单位油。

c)循环应用引理1

d)这个问题就便成了求解一个最小的N，使得

这样具体的结果大家就可以自行计算了。

引理1：wirelessyang.info

场景：在Fig2显示的图中，我们的目标在于先找到m’使得m’=min{m}，然后再这个m’的条件下找到一个x’使得x’=max{x}。

内容：m’=M; x’=Z/(2*n+1)。

证明:略。wirelessyang.info

4 汽车加油问题2(待解决)wirelessyang.info

假设有一辆车，它的油箱恰好和一个油桶一样大，而且车上恰好可以运载一个桶。假设一桶油可以让车开一百公里。现在在起点，车装满了油，另外起点还有100桶油。问，这车最远能离开起点多远？