## Airports in a Strange World

Posted by Atran on July 23, 2010 – 9:11 pm

In a strange world there are n airports arranaged around a giant circle, with exactly one airplane at each airport initially. Every day, exactly two of the airplanes fly, each going to one of its adjacent airports. Can the airplanes ever gather at one airport?

July 23rd, 2010 at 10:22 pm

Here are some preliminary thoughts:

Take N to be odd, and 3 for the sake of this example. Two planes must fly from the airports to an adjacent airport each day. Call the airports A, B and C. If the airplanes from A and C fly to B, then all airplanes are at airport B, and there is a solution to the puzzle.

Now take N to be even, and 2 for the same of argument. Both of them would have to travel to the other airport each day, making it impossible for the two airport puzzle to be solved.

At this point, it it not possible to say that only odd N is solvable, but it is a start.

July 23rd, 2010 at 10:45 pm

Yes, easily if n is odd.

The planes at the airports each side of the destination airport get there on day 1. Those two airports away need 2 days, so arrive on day 3. Three airports 3 days, arriving on day 6, and so on until we get to the (n-1)/2-th airports. These need (n-1)/2 days and arrive on day (n-1)*(n+1)/8.

It can’t be done if n is even as an odd number of steps is required to bring all planes to the one airport, and two steps must be taken each day.

July 24th, 2010 at 1:29 am

@Nathan – nice start! @Wizard – nice constructive strategy for the Nathan’s case, but not all even numbers are bad – your arguments there are not (entirely) correct

July 24th, 2010 at 2:36 am

Absolutely right, Slavy. You can do it if n is a multiple of 4.

July 24th, 2010 at 3:25 am

Now I agree Let’s make the problem one idea more challenging – assume that not 2, but k planes (of course, n is greater or equal to k) fly to a neighboring airport at each move. Can the airplanes ever gather at one airport?

July 24th, 2010 at 1:38 pm

For the case of four planes, label them A, B, C, and D.

A flies to B, and B flies to D. Then A and C fly to D. This shows that N must be greater then two for a solution to be possible.

July 24th, 2010 at 1:51 pm

Here are solutions for N = 6, 8, and 10

1 1 1 1 1 1

0 0 1 1 1 3 A and B fly to F

0 0 0 1 1 4 C flies to D, D flies to F

0 0 0 0 0 6 D and E fly to F

1 1 1 1 1 1 1 1

0 0 1 1 1 1 1 3 A and B fly to H

0 0 0 0 1 1 1 5 C and D fly to H

0 0 0 0 0 1 1 6 E flies to F, F flies to H

0 0 0 0 0 0 0 8 F and G fly to H

1 1 1 1 1 1 1 1 1 1

0 0 1 1 1 1 1 1 1 3 A and B fly to J

0 0 0 0 1 1 1 1 1 5 C and D fly to J

0 0 0 0 0 0 1 1 1 7 E and F fly to J

0 0 0 0 0 0 0 1 1 8 G flies to H, H flies to J

0 0 0 0 0 0 0 0 0 10 H and I fly to J

This suggests that there is a recursive descriptions of the solution, and that the number of moves could have a closed form to it.

July 24th, 2010 at 1:58 pm

Here are solutions for N = 5, 7, 9

1 1 1 1 1

0 0 1 1 3

0 0 0 0 5

1 1 1 1 1 1 1

0 0 1 1 1 1 3

0 0 0 0 1 1 5

0 0 0 0 0 0 7

1 1 1 1 1 1 1 1 1

0 0 1 1 1 1 1 1 3

0 0 0 0 1 1 1 1 5

0 0 0 0 0 0 1 1 7

0 0 0 0 0 0 0 0 9

The number of moves to solve this puzzle is floor(N/2)

July 25th, 2010 at 3:22 am

@Nathan – your examples are not correct The planes should fly to a neighboring airport, so B cannot fly to F (for example). Thus, when you cluster more than 2 planes at the first move in one airport, you should pay the price to have gaps and not all the occupied ones be adjacent….

July 26th, 2010 at 2:43 pm

Even number of Airports require the planes to fly to an “End” Airport. End merely means all planes must travel in only a clockwise or counter-clockwise direction to a specific airport and never leave that airport.

Airport Plane count

ABCD 1 1 1 1

1st flight round A flies to B and B flies to C. 0 1 2 1

2nd flight round B flies to C and C flies to D. 0 0 2 2

3rd flight round C flies to C and D flies to D. 0 0 0 4

Odd number airports require all planes to fly to the “middle” airport. Middle referes to 2 adjoining airports where flights leave both airports and fly opposite directions.

My brain hurts if you throw in planes can fly either direction as often as they want.

July 26th, 2010 at 3:13 pm

So what is your answer, John24? Is it every number of airports admissible? And if yes, could you provide an example for 6 airports.

July 28th, 2010 at 8:58 am

All odd number of airports is possible except for 1 airport.

All even number of airports is possible if the number of airports is evenly divisible by 4.

This is because the number of flights required by each plane when flown in pairs requires an even number of flights be flown.

If there are 8 airports and you fly to an end airport then it requires 7 ( 7 + 1 ) / 2 = 28 flights to complete. If n represents the number of airports then the formula becomes:

(n – 1) (n – 1 + 1) / 2 to determine the number of flights needed.

When flying to intermediate airports you need to adjust the formula to represent each side coming into the airport.

Example 8 airports but all planes flying to airport 2. The formula would then be

(n – 2) ( n – 2 + 1) / 2 + (m – 2) ( m – 2 + 1) / 2 = 22 flights

n represents the number of airports on side 1 and m represents the number airports on side 2.

This formula can then be modified to handle any destination airport value.

Let x represent destination airport number.

( n – x ) ( n – x + 1 ) / 2 + ( m – x ) ( m – x + 1) / 2

Summarize:

Let n be the position of the airport clockwise from the destination.

Let m be the position of the airport counter-clockwise from the destination.

Let x be the position of the destination airport.

If the final destination is either end, meaning all planes fly either clockwise or counter-clockwise and end at a final point with the one plane which never leaves its aiport, then the formula for the number of flights is

(n – 1) (n – 1 + 1) / 2

If the final destination is in the middle, meaning some planes fly clockwise and some fly counter-clockwise and end at a final point with the one plane which never leaves its aiport, then the formula for the number of flights is

( n – x ) ( n – x + 1 ) / 2 + ( m – x ) ( m – x + 1) / 2

Examples:

X = 6 airports

if n = 6 then plane at 6 needs 5 flights or n – 1 flights

if n = 5 then plane at 5 needs 4 flights or n – 1 flights

if n = 4 then plane at 4 needs 3 flights or n – 1 flights

if n = 3 then plane at 3 needs 2 flights or n – 1 flights

if n = 2 then plane at 2 needs 1 flights or n – 1 flights

if n = 1 then plane at 1 needs 0 flights or n – 1 flights

15 flights needed

X = 6 and fly to airport 2

if n = 6 then plane at 6 needs 4 flights or n – 2 flights

if n = 5 then plane at 5 needs 3 flights or n – 2 flights

if n = 4 then plane at 4 needs 2 flights or n – 2 flights

if n = 3 then plane at 3 needs 1 flights or n – 2 flights

if n = 2 then plane at 2 needs 0 flights or 2 – n flights

if n = 1 then plane at 1 needs 1 flights or 2 – n flights

11 flights needed

X = 6 and fly to airport 3

if n = 6 then plane at 6 needs 3 flights or n – 3 flights

if n = 5 then plane at 5 needs 2 flights or n – 3 flights

if n = 4 then plane at 4 needs 1 flights or n – 3 flights

if n = 3 then plane at 3 needs 0 flights or n – 3 flights

if n = 2 then plane at 2 needs 1 flights or 3 – n flights

if n = 1 then plane at 1 needs 2 flights or 3 – n flights

11 flights needed

X = 8 destination airport 1

if n = 8 then plane at 8 needs 7 flights or n – 1 flights

if n = 7 then plane at 7 needs 6 flights or n – 1 flights

if n = 6 then plane at 6 needs 5 flights or n – 1 flights

if n = 5 then plane at 5 needs 4 flights or n – 1 flights

if n = 4 then plane at 4 needs 3 flights or n – 1 flights

if n = 3 then plane at 3 needs 2 flights or n – 1 flights

if n = 2 then plane at 2 needs 1 flights or n – 1 flights

if n = 1 then plane at 1 needs 0 flights or n – 1 flights

28 flights needed

X = 8 destination airport 2

if n = 8 then plane at 8 needs 6 flights or n – 2 flights

if n = 7 then plane at 7 needs 5 flights or n – 2 flights

if n = 6 then plane at 6 needs 4 flights or n – 2 flights

if n = 5 then plane at 5 needs 3 flights or n – 2 flights

if n = 4 then plane at 4 needs 2 flights or n – 2 flights

if n = 3 then plane at 3 needs 1 flights or n – 2 flights

if n = 2 then plane at 2 needs 0 flights or n – 2 flights

if n = 1 then plane at 1 needs 1 flights or 2 – n flights

22 flights needed

X = 8 destination airport 3

if n = 8 then plane at 8 needs 5 flights or n – 3 flights

if n = 7 then plane at 7 needs 4 flights or n – 3 flights

if n = 6 then plane at 6 needs 3 flights or n – 3 flights

if n = 5 then plane at 5 needs 2 flights or n – 3 flights

if n = 4 then plane at 4 needs 1 flights or n – 3 flights

if n = 3 then plane at 3 needs 0 flights or 3 – n flights

if n = 2 then plane at 2 needs 1 flights or 3 – n flights

if n = 1 then plane at 1 needs 2 flights or 3 – n flights

18 flights needed

X = 8 destination airport 4

if n = 8 then plane at 8 needs 4 flights or n – 4 flights

if n = 7 then plane at 7 needs 3 flights or n – 4 flights

if n = 6 then plane at 6 needs 2 flights or n – 4 flights

if n = 5 then plane at 5 needs 1 flights or n – 4 flights

if n = 4 then plane at 4 needs 0 flights or n – 4 flights

if n = 3 then plane at 3 needs 1 flights or 4 – n flights

if n = 2 then plane at 2 needs 2 flights or 4 – n flights

if n = 1 then plane at 1 needs 3 flights or 4 – n flights

16 flights needed

July 28th, 2010 at 3:24 pm

The answer is correct, but the proof is still not complete and looks more like observation.

July 29th, 2010 at 3:06 am

@Atran. There are quite a lot of posts for you to approve or delete. You need to do that from your login dashboard.