Show that the number of simply connected closed paths through a 2xM rectangle grows at least as fast as M
^{7}.
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
^{7} > 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 yaxis). 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 20080328 11:15:12 