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.)
 re: A similar conclusion | Comment 4 of 6 |
(In reply to A similar conclusion by Paul)

There are actually only two ways to "decorate" an end where only the left or only the right side is at the end, as you can't add a right square to an end that has only a left square and vice versa.

As I noted in my second post, the value approaches 3.51776695 * (1+sqrt(2))^M, which is indeed exponential, but the base is less than the 3 that you indicate.
 Posted by Charlie on 2008-03-28 20:25:01

 Search: Search body:
Forums (0)