Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Stepping paths

  1. Jan 28, 2005 #1
    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.
     
  2. jcsd
  3. Jan 28, 2005 #2

    DaveC426913

    User Avatar
    Gold Member

    a LOT.....
     
  4. Jan 28, 2005 #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
     
  5. Jan 28, 2005 #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.
     
  6. Jan 28, 2005 #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: Jan 28, 2005
  7. Jan 28, 2005 #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.
     
  8. Jan 28, 2005 #7
    so for that... i have no idea :-)
     
  9. Jan 28, 2005 #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.
     
  10. Jan 29, 2005 #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: Jan 29, 2005
  11. Jan 29, 2005 #10
    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
     
  12. Jan 29, 2005 #11
    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.
     
  13. Jan 29, 2005 #12

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I know this one! It's zero! (hint: color the squares as you would on a chessboard...)
     
  14. Jan 30, 2005 #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.
     
  15. Jan 30, 2005 #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: Jan 30, 2005
  16. Jan 30, 2005 #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 (Text):

    // 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: Jan 30, 2005
  17. Jan 30, 2005 #16
    That's pretty cool.
     
  18. Feb 5, 2005 #17

    Alkatran

    User Avatar
    Science Advisor
    Homework Helper

    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...
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Stepping paths
  1. Drawing a path (Replies: 2)

  2. Shortest path (Replies: 6)

  3. Man steps through glass (Replies: 19)

  4. First steps (Replies: 20)

Loading...