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

  • Thread starter Bartholomew
  • Start date
  • Tags
    Grid
In summary, there are 184,756 different ways to walk from point (1,1) to point (10,10), using just squares (99 steps).
  • #1
Bartholomew
527
0
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.
 
Physics news on Phys.org
  • #2
a LOT....
 
  • #3
not really positive... but for just a guess i would go with
[tex]
\frac{10!}{(10-5)!5!}
[/tex]

not sure how to type 10 choose 5 in latex
 
  • #4
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.
 
  • #5
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
 
Last edited:
  • #6
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.
 
  • #7
so for that... i have no idea :-)
 
  • #8
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.
 
  • #9
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. :rolleyes:
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
 
Last edited:
  • #10
Bartholomew said:
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
 
  • #11
Problem+Solve=Reason said:
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.
 
  • #12
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...)
 
  • #13
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.
 
  • #14
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.
 
Last edited:
  • #15
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.
Code:
// 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;
}
 
Last edited:
  • #16
That's pretty cool.
 
  • #17
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...
 

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

1. What is the total number of paths from (1,1) to (10,10) in a 10x10 grid?

The total number of paths from (1,1) to (10,10) in a 10x10 grid is 184,756. This can be calculated using the binomial coefficient formula, where n = 20 and k = 10.

2. Can you explain the concept of a "path" in this context?

In this context, a path refers to a series of steps taken from the starting point (1,1) to the end point (10,10) in a 10x10 grid. Each step can be either a horizontal or vertical movement, and the goal is to reach the end point without crossing any lines or going outside the grid.

3. How does the number of paths change if the starting and ending points are different?

If the starting and ending points are different, the total number of paths will change. This is because the number of possible paths is dependent on the distance between the starting and ending points. The further apart they are, the more paths there will be.

4. Is there a quicker way to calculate the number of paths instead of using the binomial coefficient formula?

Yes, there is a quicker way to calculate the number of paths. It is known as the "Pascal's Triangle" method, where the number of paths for each point in the grid can be found by adding the number of paths from the two points directly above it. This method is more efficient for larger grids.

5. How does changing the size of the grid affect the number of paths?

As the size of the grid increases, the total number of paths also increases. This is because there are more possible routes to take from the starting point to the ending point. For example, in a 12x12 grid, there are 705,432 paths from (1,1) to (12,12), which is significantly more than in a 10x10 grid.

Similar threads

Back
Top