Subscribe via feed.

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?


This post is under “Tom” and has 14 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

14 Responds so far- Add one»

  1. 1. Nathan Said:

    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.

  2. 2. Wizard of Oz Said:

    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.

  3. 3. slavy Said:

    @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 ;)

  4. 4. Wizard of Oz Said:

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

  5. 5. slavy Said:

    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?

  6. 6. Nathan Said:

    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.

  7. 7. Nathan Said:

    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.

  8. 8. Nathan Said:

    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)

  9. 9. slavy Said:

    @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….

  10. 10. John24 Said:

    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.

  11. 11. slavy Said:

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

  12. 12. John24 Said:

    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

  13. 13. slavy Said:

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

  14. 14. Chris Said:

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

Post a reply




PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0