Will anyone provide a general formula for the edge-to-edge self-avoiding walk with Y=3?
18
250Ṁ1210
resolved Jan 4
Resolved
NO

Start with a grid of nodes that's X nodes across and Y nodes high. You're going to draw a path starting at any node on the left edge and ending at any node on the right edge. The path can only move from a node to a directly adjacent node in the vertical or horizontal direction, and it cannot touch any node twice. (It may leave a node untouched.) How many total paths are there?

  • When X is 1, the total number of paths is Y^2.

  • When Y is 1, the total number of paths is 1.

  • When Y is 2, the number of total paths is 2^(X+1).

  • For any Y > 2, Y^(X+1) is a lower bound, but the actual number of paths is much higher.

I will leave proving all of the above statements as an exercise to the reader. Past these numbers, it becomes... challenging. I want a closed-form expression for Y=3, which is restricted enough that I feel like it's still possible.

The general case where X and Y can vary arbitrarily and the path can start and end at any node has been widely studied and no solution is known.

Get
Ṁ1,000
to start trading!

🏅 Top traders

#NameTotal profit
1Ṁ230
2Ṁ114
3Ṁ23
4Ṁ21
5Ṁ18
© Manifold Markets, Inc.TermsPrivacy