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 questioned the high difficulty level of this puzzle when it was in the queue. I don't know if I'm missing something here. But in any case...

Let's restrict ourselves to a small fraction of the simply connected paths to show their number, as M gets bigger, exceeds M^7.  Consider only those paths where one side of the path is completely along x=0 with y ranging from 0 to M (i.e., along the y-axis). Let the verticals on the right side, separating each y from y+1, be some combination of x=1 segments and x=2 segments.

There are 2^M such closed paths. By definition 2^M increases exponentially, while M^7 increases only polynomially.

2^M first exceeds M^7 at M=37, when 2^37 = 137,438,953,472 and 37^7=94,931,877,133.  From there on, 2^M keeps doubling, while even the first extra member of the M^7 series multiplies by a factor of only (38/37)^7 ~= 1.205238809632966. Subsequent increments of M^7 are even smaller, while those of 2^M remain 2. 

Edited on March 28, 2008, 11:21 am

Posted by Charlie on 2008-03-28 11:15:12