Gridwalking

Given an \(m \times n\) grid, it is easy to count the total number of shortest routes from the bottom left corner to the top right corner, since every move would be either upward or rightward. However, if we remove the restriction of "shortest" and instead use the restriction that "we can repeat vertices but not edges" (to prevent the case of infinite looping), how do we count the total number of routes? The new problem looks something like this: "Given an \(m \times n\) grid, how many routes are there to travel from bottom left corner to top right corner, whereby for every route we can repeat vertices but not edges?" Let the total number of routes be \(P(m,n) \). I tried two approaches which are used to solve the original problem. Both did not work.

  1. In the original problem each shortest route has \(m+n\) steps. We have to choose \(m\) steps rightwards from the total of \(m+n\) steps, so the total number is the number of ways to arrange \(m\) step \(m+n\) positions, ie. \(\displaystyle \binom{m+n}{m}\). However, for the new problem, the steps can be up, down, left or right, and the total number of steps is not fixed. So I got stuck.

  2. Recurrence Approach: Assign coordinates to the grid with the bottom left being \((0,0)\) and the top right being \((m,n)\). To reach point \((m,n)\) we must go from either point \((m-1,n)\) or \((m,n-1)\). I was considering if the total number of routes to \((m,n)\) could be reduced to a recurrence relation in that way: \(P(m,n)=P(m-1,n)+P(m,n-1)\) But then I realised that some routes can go to \((m-1,n)\) and then go to \((m,n-1)\) before reaching \((m,n)\) and vice versa, so there could be a overcount. Furthermore, the number of ways to move from \((0,0)\) to \((m-1,n)\) is actually more than \(P(m-1,n)\) since the extra column in the \(m\times n\) grid allows routes that move through there. Likewise for \(P(m,n-1)\).

Note by Le Anh
1 week, 3 days ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)

Comments

Sort by:

Top Newest

I don't think there is a direct formula for this. You could start to calculate lower and upper bounds, for example

Upper bounds:

  • There are \( (n \cdot m)! \) different ways to reach all points but many of them aren't allowed.
  • There are at most \( (n+1) \cdot (m+1) - 1 \) steps to make and every step can go to four directions, so there are at most \( 4^{(n+1) \cdot (m+1) - 1} \) different ways.

Lower bounds:

  • As you mentioned, there are \( \binom {n+m}{m} \) shortest paths.
  • You could start categorizing the paths and calculating their numbers, but I don't really think that these bounds say very much. The upper bounds grow so much faster that the difference becomes far too big.

Maybe you should think about square grids first, or \( 1 \times n\), then \( 2 \times n \) and so on.

Henry U - 1 week ago

Log in to reply

\( 1 \times n\): \( n+1 \)

\( 2 \times n \): \( \binom {n+2}{2} \) shortest paths \( + ... \) I give up...

Henry U - 1 week ago

Log in to reply

This are very good questions and I think this is very hard to solve. Maybe you take a look at this website: https://www.adpoint.de/adwords-agentur/

Anton Goetze - 1 week ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...