Number of Ways to Walk Between Corners of Blocks

  • Context: Undergrad 
  • Thread starter Thread starter matiasmorant
  • Start date Start date
  • Tags Tags
    Combinatorics
Click For Summary

Discussion Overview

The discussion revolves around the problem of determining the number of ways to walk between corners of blocks on a grid, starting from the coordinates (0,0) to a target corner (X,Y) while walking a fixed number of block sides (N). The conversation explores various interpretations of the problem, including constraints on movement and the implications of walking more than the minimum required sides.

Discussion Character

  • Exploratory
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant proposes calculating the number of ways to walk from (0,0) to (X,Y) while walking exactly N block sides, allowing for the possibility of revisiting sides.
  • Another participant questions whether the number of possible ways is infinite, suggesting that one could keep returning to the starting point.
  • A different viewpoint suggests considering a grid of n*n square blocks and asks how many ways one can traverse the grid from one end of a diagonal to the other, with the requirement of getting closer to the destination with each move.
  • One participant clarifies that if N is not the minimum number of sides required to reach the destination, certain configurations (like reaching (1,1) in 3 sides) are impossible.
  • Another participant emphasizes that their problem differs from the previous one by allowing for movement that does not necessarily bring them closer to the destination with each step, while still requiring a fixed number of steps.
  • There is a suggestion that the solution to one participant's problem could be derived from the other by considering paths in both directions, indicating a potential relationship between the two problems.
  • A later reply introduces a reformulation of the problem, suggesting a method to calculate the number of ways based on the total steps taken and the distribution of those steps in different directions.

Areas of Agreement / Disagreement

Participants express differing views on the nature of the problem, particularly regarding the constraints on movement and the implications of walking more than the minimum required sides. There is no consensus on a single approach or solution, and multiple competing interpretations of the problem remain.

Contextual Notes

Participants have not fully resolved the assumptions regarding the nature of the paths and the constraints on movement, particularly in relation to the fixed number of steps (N) and the implications of returning to previous positions.

matiasmorant
Messages
38
Reaction score
0
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?
 
Physics news on Phys.org
hi matiasmorant! :smile:
matiasmorant said:
(I can walk over the same side more than once).

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

(i can just keep going back for my keys! :biggrin:)
 
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.
 
Last edited:
tiny-tim said:
hi matiasmorant! :smile:


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

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

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 :-)
 
Last edited:
SW VandeCarr said:
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.
 
matiasmorant said:
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.)
 
Last edited:
matiasmorant said:
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 :wink:​
 
Last edited:

Similar threads

High School Combinatorics and Magic squares
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Number of ways to go to the opposite corner.
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Average number of times a random walk passes a point
  • · Replies 10 ·
Replies
10
Views
3K
Undergrad How to implement proper error estimation using MC
  • · Replies 3 ·
Replies
3
Views
3K
Undergrad Conditional variance and total variance
  • · Replies 1 ·
Replies
1
Views
523
Undergrad Is There a Simpler Way to Calculate the Probability of a Needle Crossing a Line?
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Find an explicit formula for this n-sum problem
  • · Replies 7 ·
Replies
7
Views
3K
Undergrad Ways to put n balls in m boxes such that exactly k boxes are empty?
  • · Replies 29 ·
Replies
29
Views
6K
Construction How Can I Economically Join 3-Way Corners in Open Boxes Without Screws Crossing?
  • · Replies 42 ·
2
Replies
42
Views
9K
Undergrad Can Generating Functions Simplify the Calculation of Currency Combinations?
  • · Replies 3 ·
Replies
3
Views
2K