Number of Paths from (1,1) to (10,10) in 10x10 Grid

[Bartholomew]

How many paths of up, down, left, or right moves are there from point (1,1) to point (10,10) in a 10x10 grid of points? No path may use any square more than once. Paths may be of any length. If it's easier, say that the bottom row of pixels is connected to the top row of pixels and the left is connected to the right, so you can walk off the edge and appear on the other side.

 

[DaveC426913]

a LOT....

 

[msmith12]

not really positive... but for just a guess i would go with
<br /> \frac{10!}{(10-5)!5!}<br />

not sure how to type 10 choose 5 in latex

 

[ceptimus]

I suppose one way to get at the answer is to calculate the answer for 3 x 3 and 4 x 4 grids, etc., (which should be fairly tractable) and see if any kind of pattern or formula emerges.

 

[msmith12]

looking at this problem a little more closely...

im going to have to change my answer a little...

if you take the nxn square, and tilt it 45 degrees you can get something that looks a little like

.....X......1
...X...X......2
...X...X...X...3
...X...X...X...X....4
...e...X...X...X...e...5
...e...e...X...X...e...e...6
e...e...e...P...e...e...e...7

(so this would be a 3x3, that is extended to the triangle...

now, the number of ways to get to P is equal to 7 choose 4

so for our ten block by ten block... we get

20 choose 10

this equals 184,756 different ways...

so, if you were to walk the 20 blocks every different way in manhattan, you would have to go 277,134 miles... or, you could walk from new york to LA and back 50 times... walk around the Earth 10 times, or walk from new york, TO THE MOON!

Cheers

~matt

 

[Bartholomew]

No, the paths may be of any length. They don't have to go just up and right. They can move away from the goal at times.

 

[msmith12]

so for that... i have no idea :-)

 

[Bartholomew]

I should note that I don't know the answer either... so far I can't even think of an efficient way to generate paths with a program.

 

[Problem+Solve=Reason]

Is it 444? 81^2 taking care of quadrant 1. (11^2)*3 taking care of quadrants 2, 3, and 4. Then we add up all the possible paths per quadrant to a total of 444 paths.
That is only if we sent 2 spaces at a time, but if we where to move any number of spaces at one time the number I came up with is: 79,248,672. Don't ask me how

_____________________________________________
In seeking wisdom thou art wise; in imagining that thou hast attained it - thou art a fool.
Lord Chesterfield

 

[Problem+Solve=Reason]

No, the paths may be of any length. They don't have to go just up and right. They can move away from the goal at times.

I just read that. Sorry, but when exactly would the goal of 10,10 be attained. If that is true, then any number beyond 1 is possible.

_____________________________________
In seeking wisdom thou art wise; in imagining that thou hast attained it - thou art a fool.
Lord Chesterfield

 

[Bartholomew]

I just read that. Sorry, but when exactly would the goal of 10,10 be attained. If that is true, then any number beyond 1 is possible.

No; the path may not retrace itself, and it is limited to a 10x10 grid. There are no paths of 100 steps, for example, because there are only 100 squares total and since you start on one of them, only 99 are available as endpoints of steps.

Let's make this teaser a whole lot easier. How many paths can you find that use all the squares (99 steps)? Why is that? How about 98 steps? Assume that the grid does wrap around so you can walk off one side and appear on the corresponding square on the opposite side.

 

[Hurkyl]

Let's make this teaser a whole lot easier. How many paths can you find that use all the squares (99 steps)?

I know this one! It's zero! (hint: color the squares as you would on a chessboard...)

 

[noelhustler]

Well, I imagine this may be related to your clump query.

Looking at Self-Avoiding Walks there seems to be some solutions for limited cases but these don't really help.

 

[Bartholomew]

Yeah, it started out as kind of related but now I'm not so sure. I was thinking if I could find the probability that any 2 given squares are connected by a same-color path, I could find the average size of a clump. But now I'm not so sure how I would do that even if I had a general formula for that probability, and the article you linked to seems to suggest that no such formula is known.

The answer to the original brain teaser of this thread, with no wraparound allowed, can be found from the Mathworld article you linked to. (answer in white) 41044208702632496804, the tenth term from h ttp://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A007764 (a link from the self-avoiding rook paths part of the article).

Hurkyl: Yep.

 

[ceptimus]

I wrote a program to count the paths for smaller square boards, and got these results:

2 x 2 : 2 paths
3 x 3 : 12 paths
4 x 4 : 184 paths
5 x 5 : 8512 paths
6 x 6 : 1262816 paths
7 x 7 : 575780564 paths

It starts to become an intractable problem to simply count paths on larger boards.

// size is the maximum coordinate value allowed, and is one less than you'd think - so 7 for a chessboard
#define SIZE 6

unsigned char grid[SIZE + 1][SIZE + 1];
unsigned long solutions;

void move(int x, int y, unsigned char n)
{
    grid[x][y] = n;

    if ((x == SIZE) && (y == SIZE))
        solutions++;
    else
    {
        if ((x < SIZE) && (grid[x + 1][y] == 0)) // look right
            move(x + 1, y, n + 1);

        if ((x > 0) && (grid[x - 1][y] == 0)) // look left
            move(x - 1, y, n + 1);

        if ((y < SIZE) && (grid[x][y + 1] == 0)) //look up
            move(x, y + 1, n + 1);

        if ((y > 0) && (grid[x][y - 1] == 0)) // look down
            move(x, y - 1, n + 1);
    }
    grid[x][y] = 0;
}

int main(int argc, char* argv[])
{
    int x, y;

    for (y = 0; y <= SIZE; y++)
        for (x = 0; x <= SIZE; x++)
            grid[x][y] = 0;

    solutions = 0L;

    grid[0][0] = 1;

    move(0, 1, 2);

    printf("%lu solutions\n", solutions * 2);

    return 0;
}

 

[Bartholomew]

That's pretty cool.

 

[Alkatran]

Try simplifying the problem.
One: Only consider the paths that start by moving to the right. The ones moving up are reflections.
Two: To go from 2x2 to 3x3 you can see it as some sort of extension of the 2x2. You can enter the 2x2 grid from 2 different places: both of them have 3 different ways to reach the goal. So 2 entrences * 3 ways * 2 reflections = 12

I'll think about extending 3 to 4...