Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

enter image description here

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??

share|improve this question
    
Can the direction be reverted? –  Alex Jan 28 at 21:38
    
@Alex - I think you won't even get $5$ solutions if you don't reverse directions somewhere. –  2012ssohn Jan 28 at 21:39
    
only condition is it should not pass through the same square more than once...and of course..through diagonals –  Hari Jan 28 at 21:39
    
@2012ssohn: yeah, I got 3... –  Alex Jan 28 at 21:41

2 Answers 2

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...

share|improve this answer

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": enter image description here

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.