Results 1 to 10 of 10

Math Help - Optimization problem

  1. #1
    Junior Member
    Joined
    Jul 2010
    Posts
    52

    Optimization problem

    Being a physicist, I'm not very familiar with the optimization problems in discrete mathematis. I don't know how to formally prove the following:

    A town has n horizontal and m vertical streets aligned in a square grid so that there are n x m crossings. Neighboring crossings are distanced by a unit length. What's the smallest length of the road that one must construct so that every crossing is connected to every other by the road?

    My solution is L = n x m - 1. I've constructed numerous examples and still can't find a counterexample. But I have no idea how to prove this. Any help will be greatly appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Two thoughts come to mind: you're dealing with the taxicab geometry here. Also, I doubt very much whether you can get every crossing without your L as a minimum, because of the fencepost problem.

    Those are my thoughts.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2010
    Posts
    52
    Thank you for the links. I'm affraid I don't understand what you meant by "get every crossing without your L as a minimum".
    Follow Math Help Forum on Facebook and Google+

  4. #4
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    "Get every crossing" just a rephrase of "traverse very crossing", or "connect every crossing by a road." If you think about this problem in terms of graph theory, then your crossings are vertices, and the roads are edges. If you have n vertices, you'll require a minimum of n-1 edges to connect all the vertices. In your case, with m x n crossings (vertices), you'll need m x n - 1 roads to connect all the crossings, as a minimum. Does that clarify things?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jul 2010
    Posts
    52
    Yes, thank you, that was the argument I needed. I'm not used to think in terms of graph theory.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Just a thought here: it makes a big difference that all the crossings must be connected to all the other crossings. The basic problem in graph theory is the minimum edge cover problem. But what you're really trying to solve is a minimum connected edge cover problem, which is definitely different. Another name for this problem is the minimum spanning tree problem, where all the weights are equal. I would use the pigeon-hole principle to prove the desired result. If you use fewer edges than your L, a vertex is going to have to be omitted from the tree, right?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Jul 2010
    Posts
    52
    I think that proof by induction is the simplest one and will suffice.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Induction sounds like it would work just fine. You're planning on inducting on the number of vertices, I'm assuming?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Jul 2010
    Posts
    52
    Yes, I will prove by induction that the general vertices can be connected this way and then that one can always find a system of roads of that length.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    I think that'll work for you. Just show that the number of roads can't be less than L, and then show that you can construct a path of length L that satisfies the conditions, and you'll be done. Good luck!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Optimization Problem
    Posted in the Calculus Forum
    Replies: 0
    Last Post: February 28th 2010, 08:47 PM
  2. Optimization Problem 2
    Posted in the Calculus Forum
    Replies: 1
    Last Post: November 8th 2009, 08:59 AM
  3. Optimization Problem
    Posted in the Calculus Forum
    Replies: 1
    Last Post: November 30th 2008, 07:20 PM
  4. Optimization Problem
    Posted in the Pre-Calculus Forum
    Replies: 5
    Last Post: April 8th 2008, 05:55 PM
  5. optimization problem
    Posted in the Calculus Forum
    Replies: 2
    Last Post: November 25th 2007, 10:20 PM

Search Tags


/mathhelpforum @mathhelpforum