Number of Ways to Walk Between Corners of Blocks

[matiasmorant]

suppose that I want to walk from the corner of a block to the corner of another block (I depart from the corner of coordinates (0,0) and want to get to the corner with coordinates (X,Y), with X and Y being whole numbers. ); and I want to do so by walking N block sides (I can walk over the same side more than once).

how many ways are there of doing so?

 

[tiny-tim]

hi matiasmorant!

(I can walk over the same side more than once).

i don't get it … surely the number of possible ways is infinite?

(i can just keep going back for my keys! )

 

[SW VandeCarr]

I believe you might be thinking of a grid of say n*n square blocks. How many ways can you traverse the grid from one end of a diagonal to the other (following the orthogonal block sides) with the caveat that you must be closer to your objective with each transit of a block side. Show a general solution for any n>1.

 

[matiasmorant]

hi matiasmorant!


i don't get it … surely the number of possible ways is infinite?

(i can just keep going back for my keys! )

yes, sure, but only N times!

I can only walk N squares sides, if I keep on coming back for my keys, then I won't have enough permitted sides left to get to my destination :-D

To start with, you can take the case where N is the least number of sides in which I can reach both corners. For example, if I want to reach the corner with coordinates (1,Y) then there Y possible routes, if I want to reach the corner with coordinates (2,Y) then there are (Y^3 - Y)/6 possible routes (that's, with N being the least). what about (X,Y) ?

However, if N is not the least... let's say N=3 and I want to get to (1,1). Then, it can't be done, because, I could get there by walking 2 sides, 4 sides (coming back for my keys once), 6 sides (coming back for my keys twice), but not 3 sides.
That's it.

Some advice in the case where N is the least is also appreciated :-)

 

[matiasmorant]

I believe you might be thinking of a grid of say n*n square blocks. How many ways can you traverse the grid from one end of a diagonal to the other (following the orthogonal block sides) with the caveat that you must be closer to your objective with each transit of a block side. Show a general solution for any n>1.

That's almost what I meant :-). but withOUT the caveat that you must be closer to your objective with each transit of a block side. I have to walk N block sides before getting to my destination. I might want to get to a corner which is just a block away (0,1), but I have to walk, say, 3 sides (so I have to come back sometimes). the answer then, would be 9 possible routes, if I didn't count bad. In your problem the answer would be just 1. Besides, I couldn't get to (1,1) by walking 3 sides :-). I'm very interested in the answer to the case you explained to.

 

[SW VandeCarr]

That's almost what I meant :-)m the answer would be just 1. Besides, I couldn't get to (1,1) by walking 3 sides :-). I'm very interested in the answer to the case you explained to.

In my problem, every block would be walked on all four sides total for all paths. Also, another hint: every path is the same length (measured in block sides). Btw, I don't see it as a combinatorial problem and it's not really very hard.

EDIT: If I understand your problem correctly, my problem becomes your problem if you take all paths in both directions. That is, the solution to your problem is just twice the number of paths as mine (assuming you're defining the grid space the same way I am, as n x n square blocks with the ends of one of the diagonals defining the start and finish for all paths.)

 

[tiny-tim]

yes, sure, but only N times!
…
However, if N is not the least

ah, so the question is …

how many ways of going from (0,0) to (x,y) in x + y + 2N steps, where N is a fixed number ≥ 0

EDIT: the way to solve this would be to deal with the case of x + 2n steps sideways and y + 2(N - n) steps up, for each n ≤ N

each case would then be the problem of arranging x + 2n items in a total of x + y + 2N ​