2
$\begingroup$

Consider a 36 by 36 grid and I'm currently standing on top left corner. I want to get to the bottom right corner while stepping on each of the square exactly once. I am only allowed to move up,down,left and right. How many ways can I do this?

It makes the problem difficult to go through each square exactly once and I am not sure where to start. Thanks in advance.

$\endgroup$
  • $\begingroup$ You have to step on each box? $\endgroup$ – user732848 Aug 9 at 2:21
  • $\begingroup$ What if you had a $2$ by $2$ grid? $\endgroup$ – Angina Seng Aug 9 at 2:26
  • $\begingroup$ @Shamim Yes. I have to step on each box exactly once. $\endgroup$ – NYRAHHH Aug 9 at 2:41
  • $\begingroup$ @Angina Seng I think there is no way to do this if it is a 2 by 2 grid. $\endgroup$ – NYRAHHH Aug 9 at 2:42
  • $\begingroup$ What about if there is a 4x4 grid? How about a 3x3 grid? $\endgroup$ – Χpẘ Aug 9 at 2:43
3
$\begingroup$

HINT: Suppose that $n$ is even. Imagine that the squares of your grid are colored alternately black and white, so that every time you take a step, you move to a square of the other color.

  • In order to step on each square exactly once, how many steps must you take?
  • If the square in the upper left corner is white, what is the color of the square that you’re on after you take that many steps?
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I don't get the hints. 1) $36^2-1$ 2) black, no contradiction. I think it's the problem of counting Hamiltonoan paths on a lattice. $\endgroup$ – Alexey Burdin Aug 9 at 3:09
  • $\begingroup$ @AlexeyBurdin: But there is a contradiction: each diagonal in this coloring is monochromatic. $\endgroup$ – Brian M. Scott Aug 9 at 3:13
  • $\begingroup$ I don't see how this helps at all. There are $64$ squares, so you must take $63$ steps? How does that help find how many ways. If you start on white and take an odd number of steps, you're on black. Again, so what? How does that in any way help solve the problem as stated? $\endgroup$ – David G. Stork Aug 9 at 3:20
  • 2
    $\begingroup$ @DavidG.Stork: So see my previous comment, and remember where the path is supposed to end. $\endgroup$ – Brian M. Scott Aug 9 at 3:23
  • $\begingroup$ I of course realize the end square is diagonally opposite the starting point. Of course. So... give the next step of analysis: HOW MANY paths exist?? $\endgroup$ – David G. Stork Aug 9 at 3:53
3
$\begingroup$

Going with Angina Seng's chessboard idea: imagine your grid is marked with black & white squares like a chessboard. Suppose the top left corner where you start is a white square. Then the 2nd square has to be black, the 3rd has to be white, the 4th has to be black, etc. How many squares to you have to traverse? What color is the opposite lower right corner?

By the way, for odd sizes, the number of paths increases very quickly. There are 105 ways just on a 5 by 5 grid. See this sequence.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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