Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 3 down vote favorite

You are standing at an airport (that lies somewhere) on equator (of the earth) and have an unlimited number of identical aircrafts (same model, make and fuel capacity etc.) to make a complete trip of equator. Each of the aircraft has the fuel capacity to fly exactly 1/3 (one-third) around the earth along equator. Any flying plane can transfer fuel to any other plane in air instantaneously (without spillage) but after transfer, it should have left with sufficient fuel to come back to the airport (or get refuel again by someone else to eventually come to airport). In any case no plane should get crashed due to fuel outage.

Q(1). What is the minimum number of aircraft necessary to get one plane all the way around the equator assuming that all of the aircraft must return safely to the airport? Assume no other airport is available and unlimited supply of fuel is available (at the airport).

Q(2). What is the minimum number of aircraft necessary for a straight line to reach one of them from start to end point (assuming airport at the start point) and the fuel capacity is 1/3 (one-third) of the straight line (and other conditioned are same as that of Q1).

I can solve it using head and trial but I am looking for a mathematically way to derive the solution.

share|improve this question
1  
This is another incantation of the jeep problem - this is popular today! It was asked in a different form earlier. At least this version has a more interesting solution. – Michael Boratko Jun 12 '12 at 5:24
jeep problem is equivalent to n fleet problem but there the condition was that we can left aeroplanes in the middle just one plane should reach the destination point .... but here we can't left them in the middle... we have to bring them back to the airport safely. – Ravi Gupta Jun 14 '12 at 8:53

2 Answers

up vote 2 down vote

There is a symmetric solution with 11 aircrafts. If you manage to carry a plane with 5 assisting planes up to one third of the equator and leave it with its tank full, then let it fly through the middle third, and redo the same strategy in reverse with 5 other assisting planes, you get a solution.

Solving this kind of problem is hard, because you constantly have to maintain a delicate balance between how much you can support the aircraft while still being able to save the assisting aircrafts who in turn will need support that will have to be saved etc.

I kinda brute-forced over strategies running with time intervals of 1/6 to find this one (my first try needed a humble 20 aircrafts)

Here, I show how, with 6 aircrafts (flying at one unit of distance per unit of time and unit of fuel, where each aircraft has tank that can contain up to 6 units of fuel), you can send one of them to a distance of 12 units while still not crashing the other five. A pair $(p,f)$ denotes the number of planes $p$ with their combined fuel $f$ at that time and place. I don't detail explicitly how the fuel is distributed but you can infer it from the table easily.

$$\begin{array}c & d=0 & d=1 & d=2 & d=3 & d=4 & d=5 & d=6 & d=7\\ t=0 & (6,36) \\ t=1& & (6,30) \\ t=2 & (1,6) & & (5,24) \\ t=3 & & (2,5) & & (4,19) \\ t=4 & (2,12) & & (1,1) & & (3,14) \\ t=5 & & (3,10) & & (1,1) & & (2,10) \\ t=6 & (2,12) & & (2,5) & & & & (2,8) \\ t=7 & & (3,10) & & (1,3) & & (1,1) & & (1,5) \\ t=8 & (2,12) & & (1,5) & & (2,2)\\ t=9 & & (2,10) & & (3,4)\\ t=10 & (1,6) & & (4,6) \\ t=11 & & (5,7) \\ t=12 & (5,30) \\ \end{array} $$

Starting the solution in reverse at t=6 allows you to catch the aircraft when it reaches d=12 at time t=12, and finally to bring it at d=18 = 3 times the distance an aircraft can fly by itself.

Seeing as there is some fuel to spare sometimes and as I have almost solutions to doing the trip with 4+4+1 planes, I wouldn't be too surprised if there is a solution with only 10 aircrafts (and maybe 9).

It would be nice to know, for each $n$, the greatest distance you can possibly reach with $n$ aircrafts. Theoretically, you could do an A* search algorithm with hyperpolyedra in a phase space of dimension $2n$ to explore everything and obtain the solution after a horrifyingly long computation.

You could also write particular flight routes, deciding which aircraft meets which aircraft where and in what order, then leave unknowns for all the distances and the fuel exchanged at each meeting point, and try to solve the horrifying system of linear inequalities you obtain and get the best distance with that particular flight route. Looking at the near solutions one can brute force with 5 aircrafts, this might be doable to find the best distance for $n=5$.

share|improve this answer
From the $d=2, t=2$ point, you need to send one airplane home with $2$ units of fuel, so it seems you only have $18$ at $d=3, t=3$. Similarly, from $d=6, t=6$ you need $(2,12)$ so one can continue and one can return. – Ross Millikan Jun 14 '12 at 3:03
@Ross: At $d=2, t=2$ the plane going home only needs $1$ unit as it is about to be met by the spare plane at $d=1,t=3$ – Henry Jun 14 '12 at 8:21
Thanks. I hadn't figured that out. – Ross Millikan Jun 14 '12 at 12:36
@mercio: why to use new planes after covering the 2/3 of the total distance.... we can reuse the 5 planes used in the beginning.... hence total 6 plane? – Ravi Gupta Jun 14 '12 at 16:33
@RaviGupta : You have to start the reverse procedure at time t=6, so in this particular solution, you have all 11 planes busy for t in [6;12]. But you are right that we could reuse some of the planes at least for t in [0;6] and [12;18]. Though so far I found that they couldn't help very much, I think it's very likely that such better solutions exist out there. – mercio Jun 14 '12 at 16:59
up vote 0 down vote

Considering each aircraft has a storage capacity to travel 1/3 the distance, we need 17 aircrafts with full storage and another one with 9.3% capacity at the start point. I do not think it makes any difference whether it is on the equator or on a straight line with the same distance.

share|improve this answer
You might explain how you are going to deploy these aircraft. – Henry Jun 14 '12 at 0:12
You might also consider whether some of them can provide fuel for the departure part of the circle and later for the arrival part. – Henry Jun 14 '12 at 0:12
@Henry: This is an answer to Q(2) then. I agree, it would be nice to see the details. mercio has provided an answer to Q(1) (that I disagree with) since your comment. – Ross Millikan Jun 14 '12 at 2:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.