Show that the number of simply connected closed paths through a 2xM rectangle grows at least as fast as M⁷.

Some clarifications:

A path is simply connected if it does not contain any closed subpaths.

The 2xM rectangle encompass points [x,y] in the Cartesian plane with:

0 ≤ x ≤ 2 and 0 ≤ y ≤ M

Paths are constructed within the 2xM rectangle from vertical and horizontal segments connecting points with integral values in x and y.

An alternative statement of the problem is to show that the number of paths/M⁷ > 0 as M goes to infinity.

The boundary of the green area is just one such closed loop.

y ↑M . ... ... . 2 1 0 1 2 x

I like Charlie's solution better than mine, but since I spent the time on it I thought I'd share anyhow.

Consider the function P(M) which is the number of paths as described in the problem for a given M. Now consider P(M+1) in terms of P(smaller M). In particular, P(M+1) includes all paths that do not include a segment when y = 0 or when y = M. That is, P(M+1) > P(M-1) (M>1). But there's more. For each of these P(M-1) paths, we can extend into the "top" and "bottom" regions in at least three ways: we can do so not at all, we can extend along only one side all the way to the end (0 or M), and we can extend along only one side all the way to the end or we can extend along only one side all the way to the end and then cut across to include the segment from 0-2 at that end. As to which side to pick, we always pick the side that's close to y=0 or y=M (whichever we're aiming toward); if both sides are equally close, pick either one -- we already know we're undercounting, so leaving off a few extra won't matter.

Since there are (at least) three ways we can "decorate" each of the P(M-1) paths on either side to create a distinct P(M+1) path, each P(M-1) path generates at least 9 paths that contribute toward P(M+1). That is:

P(M+1) >= 9P(M-1)

As an equality, this sort of equation frequently has solutions of the form a^M, so let's make that substitution and solve for a, assuming that a^M is not zero.

a*a^M = 9a^M/a

a = 9/a

a^2 = 9 (if this were an inequality and a were < 0 the direction would shift)

a = 3

and so

P(M) = 3^M is one function that obeys the inequality (but still undercounts the true number of paths)

If this is so, then, as Charlie noted, the limit of 3^M/M^7 is infinite as M becomes infinite.

 

I can't help but wonder if there's something missing in our understanding of this problem, as two different approaches both give an geometric lower bound to P(M), making the choice of M^7 seem somewhat arbitrary.

Posted by Paul on 2008-03-28 20:01:28