Results 1 to 6 of 6

Thread: Travelling problem/puzzle

  1. #1
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    1,563
    Thanks
    293

    Travelling problem/puzzle

    In Flyland, each city has 2-way direct flights to a maximum of 3 other cities.
    Every city is reachable from every other city with at most 3 flights.
    What is the maximum number of cities in Flyland?

    I get 20. Anybody beat that?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    5,565
    Thanks
    2348

    Re: Travelling problem/puzzle

    what is a 2-way direct flight?

    a touch and go and returning?

    but seriously does this mean that if $(a,b)$ exists then $(b,a)$ exists and doesn't count as one of $b$'s flights?
    Last edited by romsek; Nov 2nd 2016 at 02:04 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jun 2014
    From
    Illinois
    Posts
    260
    Thanks
    89

    Re: Travelling problem/puzzle

    I think he means that if you can fly from A-to-B you can also fly from B-to-A. And that the route counts as one of the 3 available flights to A and also as one of the three available to B. But I must say, after noodling on this for a few minutes I can't get anywhere near twenty cities.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,013
    Thanks
    2551
    Awards
    1

    Re: Travelling problem/puzzle

    Quote Originally Posted by DenisB View Post
    In Flyland, each city has 2-way direct flights to a maximum of 3 other cities.
    Every city is reachable from every other city with at most 3 flights.
    What is the maximum number of cities in Flyland? I get 20. Anybody beat that?
    This is rather simple problem about connected graphs. However, I am not sure that any such graph can exist.
    It appears that the degree of any vertex has a minimum of one and a maximum of three.
    One of the most important theorems in graph theory is: $m\le \dfrac{2\|\mathscr{E}\|}{\|\mathscr{V}\|}\le M$.
    That says the minimum vertex-degree is less than or equal to twice the number of edges divided the number of vertices which is less or equal to the maximum vertex-degree.
    I cannot make your twenty work.
    Maybe your description of the graph is misleading?
    Here are two more graph facts:
    There must be at least two vertices of the same degree and an even number of odd vertices.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    1,563
    Thanks
    293

    Re: Travelling problem/puzzle

    Graph (c) on page 14 of this document is the solution:

    http://www.combinatorics.org/ ojs/index.php/eljc/article/ view/DS14/pdf
    Last edited by DenisB; Nov 2nd 2016 at 07:28 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Jun 2014
    From
    Illinois
    Posts
    260
    Thanks
    89

    Re: Travelling problem/puzzle

    The correct URL is this:

    Moore Graphs and Beyond: A survey of the Degree/Diameter Problem | Miller | The Electronic Journal of Combinatorics

    Below is the graph - but note that there are nodes with as many as six connections, which violates the premise of the puzzle (three 2-way connections per city). A better description would have been "there are at most 3 flights that may depart from any city, but an unlimited number of flights may terminate in a city."

    Travelling problem/puzzle-fly.jpg
    Last edited by ChipB; Nov 3rd 2016 at 04:41 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: Sep 27th 2012, 02:56 PM
  2. Asymmetric Travelling Salesman Problem - Particular case
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: Nov 17th 2011, 02:13 AM
  3. TSP travelling salesperson problem
    Posted in the Advanced Math Topics Forum
    Replies: 7
    Last Post: Mar 2nd 2010, 05:07 PM
  4. travelling boat problem
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: Oct 15th 2007, 08:55 PM

/mathhelpforum @mathhelpforum