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.
🏅 Top traders
# | Name | Total profit |
---|---|---|
1 | Ṁ230 | |
2 | Ṁ114 | |
3 | Ṁ23 | |
4 | Ṁ21 | |
5 | Ṁ18 |