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.)
Solution Am I missing something? (spoiler?) | Comment 1 of 6

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 y-axis). 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 2008-03-28 11:15:12

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