飞机加油问题

zhiqiang四月 3, 2008 自然科学

珍爱生命，远离政治。今天我们讨论一个数学问题。

这个问题的一个基本版本是说，有N架完全相同的飞机停留在一个机场，每一架最多装的油可以支持飞机飞行1个单位距离，飞机能够瞬时转弯，同时可以瞬时在空中互相加油。问如果要求所有起飞的飞机都安全返回机场的话，最多可以把一架飞机送出去多远距离。

解答来自胖头王：

今天吃饭跟同学聊起来之前参加数模竞赛作的一个题目，后来闲得无聊发现竟然有很多地方讨论这个问题，所以把当初的数模论文发上来。

我们给出了这个问题的渐进结果，即当 $n\rightarrow\infty$ 的时候，距离等于 $\Theta(\frac12\log n)$ 。注意因为有1/2系数，这里 $\Theta$ 的含义是说上下界最多差的是一个高阶的加法项（其实这里写的不是很严格，具体的需要看论文中的定理描述）。

[论文下载]

关于加油问题, 策略 »

摸箱子问题以及在Static data structure problems上的应用以前提到过，理论计算机这门课会邀请一些正在这边访问的教授来讲课，由于是本科生，所以这些教授一般都是讲些有趣的东西，比如之前的overhang 堆...
37-rule-is-optimal Theorem: Any protocol of date problem has success probability less than $\frac{u}{n}\sum\limits_{i=u}^{n-1}\frac1i$ which is about $37\%$. Here $u$ is the biggest number such that \(\sum_{i=u}^...
帽子游戏一在这个游戏的开头，我们设想自己要参加一个电视游戏大奖赛。规则呢，是这样。我们有 n 个人，作为一个小组来参加游戏。游戏中，主持人会给我们...
帽子游戏二这个题目听说是MSRA的面试题。在这个游戏的开头，我们设想自己要参加一个电视游戏大奖赛。规则呢，是这样。我们有 n 个人，作为一个小组来参...
策略游戏：医生和病人（I）我很早之前就想过这个问题，但一直只知道一个trivial的答案。前两天无意中发现网上已经有高手给出了更好的方案，故记录在此。有兴趣的可以自己想...
征集3个人分蛋糕的方法 Yao在课程《理论计算机II》的第一节课上提到的一个问题：三个人如何平分一块蛋糕？要求每个人拿到不少于1/3的蛋糕——这里指的是每个人认为自...
硬币游戏 Alice和Bob两人玩一种硬币游戏。游戏在一个$$2\times2$$的棋盘上进行，棋盘上每个格子上都有一枚硬币。在每一回合，Alice可以决定选择翻转某两枚或者一...
硬币游戏的答案前两天贴出了一个硬币游戏，希望寻找一种胜利策略。这是一个非常有意思的题目，没事做的时候可以用来锻炼思考能力。我迫不及待的想在这里公布...
最佳约会策略题外话：最近阅微堂发的都是网友转发的政治方面的文章，不爱看的人会比较痛苦。现在讨论一个轻松一点的话题。其问题，已经被研究了很多年，有...

8条留言 -> 跳到留言表格

At 2008.04.03 15:28, BetterWang said:

我记得有个题目是一架飞机可以绕地球飞半圈，可以无限空中加油，问需要多少架飞机可以让其中一架环绕地球一整圈。

[Reply]
- At 2008.04.03 20:37, zhiqiang said:
  
  绕地球一圈和原路返回没有区别，你说的是文中模型的一个特例
  
  [Reply]
  - At 2008.06.20 15:15, ada said:
    
    绕地球一圈和原路返回是有区别的
    
    [Reply]
    - At 2008.06.20 16:06, zhiqiang said:
      
      我又想了一下，如果飞机可以两个方向飞，绕一圈和原路返回就是一回事了。
      
      如果只能往一个方向飞，的确不是一回事，我搞错了。但我想和飞2倍距离是不是一样的？如果这样的话还是包含在论文的讨论范围之内。
      
      [Reply]
At 2008.04.04 16:09, coredream said:

一直忘记过来谢谢zhiqiang帮忙验证google apps，好人一个，我代表全公司谢谢你了！

[Reply]
At 2008.04.06 08:49, 爽歪歪 said:

你好感觉你对金融很在行我现在大学向转专业学金融能不能帮我介绍几本比较好的金融书籍啊？

[Reply]
- At 2008.04.06 08:58, zhiqiang said:
  
  对于理论计算机，我们还可以讨论一下。
  
  看过几本经济学的书，但对金融一点都不懂。所以不知你怎么得出我对金融在行的？
  
  [Reply]
At 2009.03.23 15:28, Mokey said:

我是Mokey，你的校友。关于飞机加油问题，我给你写了一封邮件，请帮助答疑解惑。
谢谢！
Mokey

[Reply]

« Perfect Shuffle的算法

firefox的代言人 »

飞机加油问题

阅微堂