All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Dao Juxing (The way of the rectangle) (Posted on 2008-03-28)

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

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/M7 > 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

 No Solution Yet Submitted by FrankM Rating: 3.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 actual numbers | Comment 2 of 6 |

Among the paths for a given M, some will extend all the way from y=0 to y=M, therefore having a height of M. Others that will fit within the grid are those of shorter heights, with those of height h being able to be positioned in any of (M+1-h) levels within the grid.

As M changes to M+1, any previous path that used the full height M that had the left side (x=0 to x=1) drawn in, or had the full width drawn in, will allow a new full height M+1 to be created. Similarly for either the right or the full width leading to another right-only top. A full width path of full height M+1 can be made from any of the three types of full-height M paths: left, right or both.

The table below was constructed with the above recurrence relations. The first row was created manually for M=1, and the remainder by computer program, shown below. There's a square on the left, a square on the right, or a rectangle that covers both, for a total of 3.

The next row, for M=2 allows us to follow the recurrences mentioned. The single square at the left from row 1, or the rectangle with both squares of height 1, can be extended to produce 2 possible paths that have only the left side at the top drawn. Similarly for the right only. The height-1 rectangle can be extended to a square, and the single-squares of height 1 can be extended to upside-down L's, either forward or reflected, giving three paths of height exactly 2 that have the whole width (2) used at the top.  This makes 7 altogether of paths that are exactly 2 high. One can see that this is correct, as: 1 2x2 square, 4 L shapes lacking one of the four subsquares, and 2 vertical rectangles (left and right). To this are added the height-1 values, either at the base or moved up one level, giving a total of 13 possibilities.

`         top         top          top          total M     at left     at right    along both   Exact height    total  ratio to previous 1           1           1           1            3             3 2           2           2           3            7            13  4.33333333 3           5           5           7           17            40  3.07692308 4          12          12          17           41           108  2.70000000 5          29          29          41           99           275  2.54629630 6          70          70          99          239           681  2.47636364 7         169         169         239          577          1664  2.44346549 8         408         408         577         1393          4040  2.42788462 9         985         985        1393         3363          9779  2.4205445510        2378        2378        3363         8119         23637  2.4171183111        5741        5741        8119        19601         57096  2.4155349712       13860       13860       19601        47321        137876  2.4148101413       33461       33461       47321       114243        332899  2.4144811314       80782       80782      114243       275807        803729  2.4143328815      195025      195025      275807       665857       1940416  2.4142665016      470832      470832      665857      1607521       4684624  2.4142369517     1136689     1136689     1607521      3880899      11309731  2.4142238518     2744210     2744210     3880899      9369319      27304157  2.4142180719     6625109     6625109     9369319     22619537      65918120  2.4142155420    15994428    15994428    22619537     54608393     159140476  2.4142144221    38613965    38613965    54608393    131836323     384199155  2.4142139422    93222358    93222358   131836323    318281039     927538873  2.4142137223   225058681   225058681   318281039    768398401    2239276992  2.4142136324   543339720   543339720   768398401   1855077841    5406092952  2.4142135925  1311738121  1311738121  1855077841   4478554083   13051462995  2.4142135826  3166815962  3166815962  4478554083  10812186007   31509019045  2.4142135727  7645370045  7645370045 10812186007  26102926097   76069501192  2.4142135628 18457556052 18457556052 26102926097  63018038201  183648021540  2.4142135629 44560482149 44560482149 63018038201 152139002499  443365544387  2.41421356`

We see that the sequence of all paths for M=1, 2, ... is 3, 13, 40, 108, 275, etc. This is sequence A059020 in Sloane's online encyclopedia of integer sequences, which points out that another recursion formula would be  a(n)=2a(n-1)+a(n-2)+4n-1, so as to necessitate keeping only two generations back, rather than all the way back to the beginning of the table the way I did in the program shown below.

The last column above shows the ratio of the value for each M to the value for M-1. This approaches sqrt(2)+1. The ratio of the number of paths to (sqrt(2)+1)^M approaches 3.51776695.

DEFDBL A-Z
CLS
max = 29
DIM ofHeight(max)

level = 1
leftOnly = 1: rightOnly = 1: both = 1: ofHeight(1) = 3: tot = 3
FOR level = 2 TO max
newLeft = leftOnly + both
newRight = rightOnly + both
newBoth = leftOnly + rightOnly + both
leftOnly = newLeft
rightOnly = newRight
both = newBoth
totExact = leftOnly + rightOnly + both
ofHeight(level) = totExact
prevTot = tot
tot = 0
FOR i = 1 TO level
tot = tot + ofHeight(i) * (level + 1 - i)
NEXT
PRINT USING "### ########### ########### ########### ############ ############# ##.########"; level; leftOnly; rightOnly; both; ofHeight(level); tot; tot / prevTot
NEXT

Edited on March 28, 2008, 2:52 pm

Edited on March 28, 2008, 2:54 pm
 Posted by Charlie on 2008-03-28 14:50:35

 Search: Search body:
Forums (0)