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: That's puzzling (to Charlie) Comment 6 of 6 |
(In reply to That's puzzling (to Charlie) by FrankM)

I can't really follow what is being said in your description. I imagine I might have been able to understand it better if you could have included illustrations, but that's not possible here.

I do note your sentence "We will show that there is a subset of paths whose cardinality includes a term in M^7".  Of course a subset can be very much smaller in cardinality than the whole set. I don't know if that's the cause of the discrepancy here, as I can't follow the argument.  Also, even a series for an exponential function includes along the way a term with a seventh power, but then goes on to infinitely high powers.  I can't tell if this applies to your argument either.

Note that in my second posting, I present the exact numbers for cases up to M=29, and I link to the On-line encyclopedia of integer sequences, where the formula given is also recursive. No closed form solution is given.  I would think that if one existed, Sloane would have it. They present it in the form of adjacent squares, emphasizing the green area rather than its boundary (and calling it red, apparently for historical reasons, in some prior person's presentations).


  Posted by Charlie on 2008-03-29 01:37:26
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 (1)
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