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.

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.
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 an 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)$ .

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
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"

Math

Appears 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}

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered 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"

Math	Appears 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

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 - 2 years, 6 months ago

$1 \times n$ : $n+1$

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

I'm thinking of creating an algo to find all possible ways then we can form a conjecture about this.

Le Anh - 2 years, 5 months ago

@Le Anh – This is a good way! Let me know about the results. Thanks!

Henry U - 2 years, 5 months ago

Just resurrecting this question - it seems very interesting! Did you manage to get any numerical data? There's one point that seems slightly ambiguous. What exactly counts as a path? Is it the collection of edges that are traversed, or is it the order that the points are visited in?

As an example of what I mean, in the diagram you provided, you could visit the points in the order $(0,0),(0,2),(3,2),(3,1),(1,1),(1,0),(2,0),(2,3),\ldots$ , or you could visit them in the order $(0,0),(0,2),(2,2),(2,0),(1,0),(1,1),(3,1),(3,2),(2,2),(2,3),\ldots)$ . Both use the same edges, and obey the rules, but are they the same path? (I'll try to upload a diagram, not quite sure how to do it in comments)

Some general thoughts:

if there are $E$ edges in total, there are $2^E$ possible sets of edges that are used in the path. You can work out if any particular set of edges works by checking the degrees of the all the vertices; the bottom-left and top-right vertices must have degree $1$ , and all others must have even degree. (Note that if the order in which the edges are traversed matters, this approach is not all that helpful. Also, $2^E$ grows very quickly with the size of the grid. Might still be useful for small grids, though)
if the order of the edges matters, a recursive search algorithm might be a good way to go. You can store "used" edges, and terminate the algorithm when the top-right point is reached, or when there are no available edges. Again, the number of possible paths grows quickly, but it could be useful for getting some numerical data together.

Let me know if this is still of interest to you (or if you managed to find a solution!)

Chris Lewis - 2 years, 3 months ago

Hi Chris, let us say the path would be the collection of edges. So the two ways of visiting the points you stated would be considered as one "path" (since I think the other way around would be more complicated). Unfortunately I haven't managed to find a solution. Your second comment is really worth a try.

Le Anh - 2 years, 3 months ago

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 - 2 years, 6 months ago

Math	Appears 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}$