10
$\begingroup$

OK, here's an easy and nice one:

Points $A$ and $B$ are separated by two rivers. One bridge is to be built across each river so as to minimize the length of the shortest path from $A$ to $B$. (Assume you can't travel on water.) Where should they be placed? Example of placing bridges (non-optimal) Author: Titu Andreescu and Răzvan Gelca

Clarifications

  1. Each river is an infinite rectangular strip (i.e., each of them has the same width everywhere), and they may not be parallel.
  2. Each bridge must be a straight segment perpendicular to the sides of the river.
  3. Assume that $A$ and $B$ are "sufficiently far" from the intersection of the two rivers.
  4. This is a purely geometrical puzzle; no tricks/ cheating/ wordplay.
  5. An answer should ideally contain a method for determining the positions of the bridges, and a proof that this method works.
$\endgroup$
15
$\begingroup$

If you could "contract" the rivers in a line, the shortest path would be to draw a straigh between AB. As you have no choice of direction in the river, the shortest path is to consider that there is no rivers : you contract the river, find the solution, decontract the rivers.

How to find the shortest path :

  • If the river has a width of $l$, draw $A'$ at distance $l$ of $A$ in direction of the river
  • Draw $B'$ the same way. This simulate the 2 rivers "contracted in a line"
  • Draw the line $A'B'$
  • Break the line at the inner side of the rivers, and move the piece from $A'$ to $A$ and from $B'$ to $B$

Picture :

enter image description here

It is the shortest path because :

this problem is totally equivalent to find the shortest path when the river are contracted in a line (because you have no choice in the river).

$\endgroup$
  • $\begingroup$ Nice answer. One remark though: how would this work if A' or B' would end up within the river, or even on the other side of the river? Imagine the river is width X, and A is X-2 units away from the river? $\endgroup$ – Nzall Jun 22 '16 at 11:21
  • 1
    $\begingroup$ The river has zero width when contracted, so to end up "in" it, A' must be at distance 0 from it, and therefore A is exactly on the furthest shoreline from B. Then the bridge placement is trivial, it goes across from A itself. $\endgroup$ – Nij Jun 22 '16 at 12:49
1
$\begingroup$

My initial thoughts (brief because I'm at work).

1) Draw the line representing the shortest distance from A to B.
2) Take points a' and b' where both lie on this line, inside the bounds of rivers A and B respectively, and are equidistant from the river banks (in other words, the points of the line that are in the middle of the rivers).
3) There is only one bridge which each of these points can lie on. Draw these bridges.
4) The path is then just straight connecting the two points to the nearest endpoint of the relevant bridge.

$\endgroup$
  • $\begingroup$ Sorry, I checked with GeoGebra, but your algorithm doesn't seem to give the minimal path in general. $\endgroup$ – Ankoganit Jun 22 '16 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.