Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
- - - - -

building a bridge


Best Answer Anza Power, 24 September 2013 - 09:40 PM

Spoiler for simple reasoning

 
Well, except that we are given the river as is, with a fixed width and a bridge perpendicular to its flow.
We do not know whether the line joining the cities lines up with the bridge - a very special case with a trivial solution.
We also do not know that the cities are equidistant from the river - a fact that bears on bridge placement if is not parallel to the joining line.
 
I'm curious to know the two different ways BMAD has to optimize the bridge placement.


You might've misunderstood me a little bit, I should have detailed a bit more, let the river be of width 1 unit, align the axis such that the x axis is parallel with and centered the river, in other words the river would be the area -0.5<y<0.5, now "removing" the river means collapsing it and so every point that was below it now goes up by 0.5 units and every point above it goes doen 0.5 units... Go to the full post


  • Please log in to reply
9 replies to this topic

#1 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1702 posts
  • Gender:Female

Posted 23 September 2013 - 01:19 PM

Suppose we have to build a road from city A to city B, but these cities are separated by a river (straight, consistent width). We would like to minimize the length of the road between these cities and the bridbe must be constructed perpendicular to the banks of the river. Where to build the bridge as to minimize the total length of the road?

I know two different ways to solve this problem. Can you find both?
  • 0

#2 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5918 posts
  • Gender:Male
  • Location:New York

Posted 23 September 2013 - 08:53 PM

Spoiler for The easiest solution


Edited by bonanova, 23 September 2013 - 09:21 PM.
Further thought

  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#3 Anza Power

Anza Power

    Junior Member

  • Members
  • PipPip
  • 80 posts

Posted 23 September 2013 - 10:33 PM

Spoiler for simple reasoning

  • 0

#4 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1462 posts
  • Gender:Male

Posted 24 September 2013 - 03:47 AM

Are you sure about that?

Consider the scenario where the river does not lie halfway between city A and city B. In fact, suppose it lies right next to city A and is at a 45 degree angle. A drawing would help.

Towns and bridge.jpg

If the center of the bridge lies on the line from A to B, then you follow the solid line. If the start of the bridge lies at the city gates of A, then you follow the dot-dash line.

If you were to make city A very small (unlike in the drawing), and you omit the potions of these paths that cross over the bridge (because they will be the same length on the two paths), it should be clear that you could move that bit of the solid line from city A to the bridge up so it would connect the end of the solid line from city B to the bridge and the end of the dot-dash line from city B to the bridge so they form a triangle. And it will then be instantly obvious that the dot-dash path is shorter than the solid line path.

I started trying to do the math to solve for the distances explicitly, and it looks too hard for me.

Edit: Saw that Bonanova edited. And:
Spoiler for

Edited by plasmid, 24 September 2013 - 03:58 AM.

  • 0

#5 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5918 posts
  • Gender:Male
  • Location:New York

Posted 24 September 2013 - 04:09 PM

Spoiler for simple reasoning

 

Well, except that we are given the river as is, with a fixed width and a bridge perpendicular to its flow.

We do not know whether the line joining the cities lines up with the bridge - a very special case with a trivial solution.

We also do not know that the cities are equidistant from the river - a fact that bears on bridge placement if is not parallel to the joining line.

 

I'm curious to know the two different ways BMAD has to optimize the bridge placement.


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#6 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5918 posts
  • Gender:Male
  • Location:New York

Posted 24 September 2013 - 04:15 PM

Are you sure about that?

Consider the scenario where the river does not lie halfway between city A and city B. In fact, suppose it lies right next to city A and is at a 45 degree angle. A drawing would help.

attachicon.gifTowns and bridge.jpg

If the center of the bridge lies on the line from A to B, then you follow the solid line. If the start of the bridge lies at the city gates of A, then you follow the dot-dash line.

If you were to make city A very small (unlike in the drawing), and you omit the potions of these paths that cross over the bridge (because they will be the same length on the two paths), it should be clear that you could move that bit of the solid line from city A to the bridge up so it would connect the end of the solid line from city B to the bridge and the end of the dot-dash line from city B to the bridge so they form a triangle. And it will then be instantly obvious that the dot-dash path is shorter than the solid line path.

I started trying to do the math to solve for the distances explicitly, and it looks too hard for me.

Edit: Saw that Bonanova edited. And:

Spoiler for

 

I agree. And my edit was meant to debunk my first notion.

 

I did the calculation for three bridge placements in the (easiest) case of placing A on the river's edge, very similar to your drawing. The three placements had the east end, the west end and the middle of the bridge on the joining line. My code for the middle placement had an error, but it was clear that that case would not minimize the road length - the east-end placement was going to be the best of the three.

 

The considerations I posted above to AP come into play, and I agree the general case is far from trivial -- both to calculate and to optimize. I think it can be done, but I put it away last night for possibly another time.


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#7 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1702 posts
  • Gender:Female

Posted 24 September 2013 - 06:46 PM

Spoiler for Hint for the complicated solution

  • 0

#8 Anza Power

Anza Power

    Junior Member

  • Members
  • PipPip
  • 80 posts

Posted 24 September 2013 - 09:40 PM   Best Answer

Spoiler for simple reasoning

 
Well, except that we are given the river as is, with a fixed width and a bridge perpendicular to its flow.
We do not know whether the line joining the cities lines up with the bridge - a very special case with a trivial solution.
We also do not know that the cities are equidistant from the river - a fact that bears on bridge placement if is not parallel to the joining line.
 
I'm curious to know the two different ways BMAD has to optimize the bridge placement.


You might've misunderstood me a little bit, I should have detailed a bit more, let the river be of width 1 unit, align the axis such that the x axis is parallel with and centered the river, in other words the river would be the area -0.5<y<0.5, now "removing" the river means collapsing it and so every point that was below it now goes up by 0.5 units and every point above it goes doen 0.5 units...
  • 0

#9 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1462 posts
  • Gender:Male

Posted 25 September 2013 - 04:04 AM

Ah, I understand Anza's answer better now. If you actually do "warp the map" by cutting out the river completely and dragging the two halves of land together and stitching them up, then drawing a straight line over the remaining land would give you the shortest path (excluding the bridge), and the point at which that line crosses the scar left by the removed river would tell you where the bridge should be. That as well as the spoiler in my post above should, I think, qualify as two ways to go about it without the hard math. Anza's approach is better because it would tell you exactly where to place the bridge, not just tell whether or not you've found the best spot and which way to nudge the bridge if it's not optimally placed.


  • 0

#10 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1702 posts
  • Gender:Female

Posted 25 September 2013 - 05:00 AM

Yes. Anza identified the easier method


  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users