how many ways to go from place a to place b through 9 squares

Question

Please see the image. How many ways are there from M to N without passing through the sqaure more than once... I counted upto 6 ways...is it the right answer??

Answer 1

The answer is $E$. Here are the paths:

1. $(0,0) \rightarrow (1,1) \rightarrow (2,2) \rightarrow (3,3)$
2. $(0,0) \rightarrow (1,1) \rightarrow (2,0) \rightarrow (3,1) \rightarrow (2,2) \rightarrow (3,3)$
3. $(0,0) \rightarrow (1,1) \rightarrow (0,2) \rightarrow (1,3) \rightarrow (2,2) \rightarrow (3,3)$
4. $(0,0) \rightarrow (1,1) \rightarrow (0,2) \rightarrow (1,3) \rightarrow (2,2) \rightarrow (1,1) \rightarrow (2,0) \rightarrow (3,1) \rightarrow (2,2) \rightarrow (3,3)$
5. $(0,0) \rightarrow (1,1) \rightarrow (0,2) \rightarrow (1,3) \rightarrow (2,2) \rightarrow (3,1) \rightarrow (2,0) \rightarrow (1,1) \rightarrow (2,2) \rightarrow (3,3)$
6. $(0,0) \rightarrow (1,1) \rightarrow (2,2) \rightarrow (1,3) \rightarrow (0,2) \rightarrow (1,1) \rightarrow (2,0) \rightarrow (3,1) \rightarrow (2,2) \rightarrow (3,3)$
7. $(0,0) \rightarrow (1,1) \rightarrow (2,2) \rightarrow (3,1) \rightarrow (2,0) \rightarrow (1,1) \rightarrow (0,2) \rightarrow (1,3) \rightarrow (2,2) \rightarrow (3,3)$
8. $(0,0) \rightarrow (1,1) \rightarrow (2,0) \rightarrow (3,1) \rightarrow (2,2) \rightarrow (1,1) \rightarrow (0,2) \rightarrow (1,3) \rightarrow (2,2) \rightarrow (3,3)$
9. $(0,0) \rightarrow (1,1) \rightarrow (2,0) \rightarrow (3,1) \rightarrow (2,2) \rightarrow (1,3) \rightarrow (0,2) \rightarrow (1,1) \rightarrow (2,2) \rightarrow (3,3)$

I hope I didn't mess that up...

Answer 2

First observation: at each step moving along a diagonal you change both x- and y- coordinate by 1, so that they both remain either even or odd. This means that you can possibly cross each square following one of the two diagonals only, and the requirement that you never cross the same square twice is equivalent to the requirement that you never follow the same path (in either direction) twice.

To illustrate the point, here is the picture with all "roads":

Now, note that the first step is always (1,1), and the last is from the point (2,2). The question is how many paths are there such that you never step on the same road section twice.

a) If after the first step you never return to (1,1), then there are, obviously, 3 ways to reach (2,2): straightforward, or taking the left or the right roads.

b) If you ever return to (1,1), then it means you at first follow smaller left circle (in either direction), or smaller right circle (in either direction), or the big circle around (also in either direction), and then you have only one way to proceed.

Overall, you have 3+2+2+2=9 ways to do this.