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

Home > Shapes
Dao Juxing (The way of the rectangle) (Posted on 2008-03-28) Difficulty: 4 of 5

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

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information