5 fixed a typo

Here's a variant on Joseph O'Rourke's construction that produces $2^{n/2}$ paths. I don't have Joseph's knack for drawing pictures, so I'll describe it in words with an example. (I'd be delighted if he would replace my words with a picture.)

Let's connect the origin $(0,0)$ to $(0,10)$. Start by laying down a series of extremely long, extremely skinny, "blue" triangles that come in horizontally from the left to $(1,1)$, from the right to $(-1,3)$, from the left to $(1,5)$, from the right to $(-1,7)$, and from the left to $(1,9)$. At this point there's just one shortest path, which zigzags from $(0,0)$ to $(1,1)$ to $(-1,3)$ to $(1,5)$ to $(-1,7)$ to $(1,9)$ to $(0,10)$. Now on each of these segments put one of O'Rourke's little yellow "splitters" -- in particular, say, at $(0,2)$, $(0,4)$, $(0,6)$, and $(0,8)$.

In general, if you use $k$ long blue triangle to create a zigzag path and put a yellow splitter on each of the $k+1$ segments of the zigzag, you get $2^{[(n+1)/2]}$ shortest paths, where $n=2k+1$.

Added later on 5/1/12: Let me paint another word picture of a construction that's better in a couple of respects. For one, it answer's Gerhard Paseman's concern over alternative shorter paths sneaking in. It also makes clear that the construction can be continued indefinitely, with the number of shortest paths doubling with each pair of additional triangles (one "blue" and one "yellow").

Suppose we have an infinite supply of long, thin blue triangles ready to come in horizontally, all from the right, at heights $1, 1/2, 1/3, 1/4$, etc. Let's start with the shortest path from $(0,2)$ to $(0,0)$ -- i.e., a vertical line segment -- and imagine it as a rubber band. Now bring in the first $n$ blue triangles, at heights $1$ to $1/n$, and poke the rubber band over so that, starting at $(0,2)$, it now follows line segments of slope $1, 2, 3, \ldots, n$ and negative something to $(0,0)$. (It shouldn't be hard to work out exactly where the poke points are and what the final negative-something slope is, but the odds of my doing so correctly are vanishingly small, and it's really not necessary for the argument, which is mainly qualitative.)

If you draw the picture (and I'm hoping Joseph will do so again!), it's easy to see that the path to this point has length less than 5 (it's shorter than the path from $(0,2)$ to $(-2,2)$ (-2,0)$to$(0,0)$), so if we assume the blue triangles are of length, say 10, we don't have to worry about anything sneaking around them. It's also easy to see that it's possible to put a tiny yellow "splitter" at the midpoint of each segment of positive slope that can't "see" anything of interest along the rubber band beyond the blue triangles that define its segment. This gives$2^n$shortest paths using$2n$triangles, with the option of letting$n$go to infinity without having to change anything that's already in place. Note: It's worth adding that this still doesn't solve the original problem of determining the maximum possible number of shortest paths when you put triangular obstacles between two points (or if it does, it does so without any proof). It just gives a lower bound on what can be done. 4 added 282 characters in body Here's a variant on Joseph O'Rourke's construction that produces$2^{n/2}$paths. I don't have Joseph's knack for drawing pictures, so I'll describe it in words with an example. (I'd be delighted if he would replace my words with a picture.) Let's connect the origin$(0,0)$to$(0,10)$. Start by laying down a series of extremely long, extremely skinny, "blue" triangles that come in horizontally from the left to$(1,1)$, from the right to$(-1,3)$, from the left to$(1,5)$, from the right to$(-1,7)$, and from the left to$(1,9)$. At this point there's just one shortest path, which zigzags from$(0,0)$to$(1,1)$to$(-1,3)$to$(1,5)$to$(-1,7)$to$(1,9)$to$(0,10)$. Now on each of these segments put one of O'Rourke's little yellow "splitters" -- in particular, say, at$(0,2)$,$(0,4)$,$(0,6)$, and$(0,8)$. In general, if you use$k$long blue triangle to create a zigzag path and put a yellow splitter on each of the$k+1$segments of the zigzag, you get$2^{[(n+1)/2]}$shortest paths, where$n=2k+1$. [Added by O'Rourke] Added later on 5/1/12: Let me paint another word picture of a construction that's better in a couple of respects. For one, it answer's Gerhard Paseman's concern over alternative shorter paths sneaking in. It also makes clear that the construction can be continued indefinitely, with the number of shortest paths doubling with each pair of additional triangles (one "blue" and one "yellow"). Suppose we have an infinite supply of long, thin blue triangles ready to come in horizontally, all from the right, at heights$1, 1/2, 1/3, 1/4$, etc. Let's start with the shortest path from$(0,2)$to$(0,0)$-- i.e., a vertical line segment -- and imagine it as a rubber band. Now bring in the first$n$blue triangles, at heights$1$to$1/n$, and poke the rubber band over so that, starting at$(0,2)$, it now follows line segments of slope$1, 2, 3, \ldots, n$and negative something to$(0,0)$. (It shouldn't be hard to work out exactly where the poke points are and what the final negative-something slope is, but the odds of my doing so correctly are vanishingly small, and it's really not necessary for the argument, which is mainly qualitative.) If you draw the picture (and I'm hoping Joseph will do so again!), it's easy to see that the path to this point has length less than 4 5 (it's shorter than the path from$(0,2)$to$(-1,2)$to$(-1,0)$(-2,2)$ to $(0,0)$), so if we assume the blue triangles are of length, say 10, we don't have to worry about anything sneaking around them. It's also easy to see that it's possible to put a tiny yellow "splitter" at the midpoint of each segment of positive slope that can't "see" anything of interest along the rubber band beyond the blue triangles that define its segment. This gives $2^n$ shortest paths using $2n$ triangles, with the option of letting $n$ go to infinity without having to change anything that's already in place.

Note: It's worth adding that this still doesn't solve the original problem of determining the maximum possible number of shortest paths when you put triangular obstacles between two points (or if it does, it does so without any proof). It just gives a lower bound on what can be done.

Let's connect the origin $(0,0)$ to $(0,10)$. Start by laying down a series of extremely long, extremely skinny, "blue" triangles that come in horizontally from the left to $(1,1)$, from the right to $(-1,3)$, from the left to $(1,5)$, from the right to $(-1,7)$, and from the left to $(1,9)$. At this point there's just one shortest path, which zigzags from $(0,0$ (0,0)$to$(1,1)$to$(-1,3)$to$(1,5)$to$(-1,7)$to$(1,9)$to$(0,10)$. Now on each of these segments put one of O'Rourke's little yellow "splitters" -- in particular, say, at$(0,2)$,$(0,4)$,$(0,6)$, and$(0,8)$. Added later on 5/1/12: Let me paint another word picture of a construction that's better in a couple of respects. For one, it answer's Gerhard Paseman's concern over alternative shorter paths sneaking in. It also makes clear that the construction can be continued indefinitely, with the number of shortest paths doubling with each pair of additional triangles (one "blue" and one "yellow"). Suppose we have an infinite supply of long, thin blue triangles ready to come in horizontally, all from the right, at heights$1, 1/2, 1/3, 1/4$, etc. Let's start with the shortest path from$(0,2)$to$(0,0)$-- i.e., a vertical line segment -- and imagine it as a rubber band. Now bring in the first$n$blue triangles, at heights$1$to$1/n$, and poke the rubber band over so that, starting at$(0,2)$, it now follows line segments of slope$1, 2, 3, \ldots, n$and negative something to$(0,0)$. (It shouldn't be hard to work out exactly where the poke points are and what the final negative-something slope is, but the odds of my doing so correctly are vanishingly small, and it's really not necessary for the argument, which is mainly qualitative.) If you draw the picture (and I'm hoping Joseph will do so again!), it's easy to see that the path to this point has length less than 4 (it's shorter than the path from$(0,2)$to$(-1,2)$to$(-1,0)$to$(0,0)$), so if we assume the blue triangles are of length, say 10, we don't have to worry about anything sneaking around them. It's also easy to see that it's possible to put a tiny yellow "splitter" at the midpoint of each segment of positive slope that can't "see" anything of interest along the rubber band beyond the blue triangles that define its segment. This gives$2^n$shortest paths using$2n$triangles, with the option of letting$n\$ go to infinity without having to change anything that's already in place.