I want to see more!

I will walk from A to B moving only North and East along the grid lines. Then, I will walk back to A along the gridlines, visiting only locations that I have not visited before.

How many paths are there from A to B that allow me to walk back to A in this way?


The green path on the left allows me to walk back to A visiting only new locations, but the orange path on the right does not. The green path on the left allows me to walk back to A visiting only new locations, but the orange path on the right does not.

24 30 36 42

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

6 solutions

Jimin Khim Staff
Nov 4, 2017

First of all, recall the following theorem in this wiki :

There are exactly ( m + n n ) \binom{m+n}{n} paths from the bottom-left corner to the top-right corner in an m × n m \times n grid.

So, without any restrictions, there are ( 3 + 5 5 ) = ( 3 + 5 3 ) = 56 \binom{3+5}{5}=\binom{3+5}{3}=56 paths from A to B.

Now, as shown in the diagram to the right, if the path is A A v B v B , A \to A_v \to \cdots \to B_v \to B, there is no way for my returning path B A B\to A not to meet the path A B . A \to B. (You need to convince yourself of this by visualizing the crossing paths in your mind.) So, I need to avoid the path A v B v , A_v \to B_v, the possible number of which is ( 1 + 5 1 ) = 6. \binom{1+5}{1}=6.

Similarly, if the path is A A h B h B , A \to A_h \to \cdots \to B_h \to B, again there is no way for me not to cross the path A B A \to B on my returning trip. (The subscripts v v and h h stand for "vertical" and "horizontal", respectively.) So, I need to avoid the path A h B h , A_h \to B_h, the possible number of which is ( 3 + 3 3 ) = 20. \binom{3+3}{3}=20.

Therefore, our answer is 56 6 20 = 30. 56-6-20=30.

However, we can do better by thinking conversely. If I take either the path A A v B h B A \to A_v \to \cdots \to B_h \to B or the path A A h B v B , A \to A_h \to \cdots \to B_v \to B, I can always avoid any grid point already visited, on my returning trip.

So, our answer again is ( 4 + 2 2 ) + ( 4 + 2 2 ) = 15 + 15 = 30. \binom{4+2}{2}+\binom{4+2}{2}=15+15=30.\ _\square

Whoa! this is a really nice problem!

Alex Segesta - 3 years, 6 months ago

I've tried solving it with permutations but was never getting a valid result because i was only looking at half the picture. It always takes 8 steps to get from A to B following the rules. I figured the first step has to be north and the last hast to be east so there are only 6 steps remaining. 2 of those steps have to be taken north, while 4 have to be taken east. So i calculated how many possibilites there are to arrange 2xEast + 4xNorth: 6! / (4! * 2!) = 15 I just failed to get to the last step and multiply it by 2 for the 2nd solution where you start with a step to the east and finish with a step to the north.

Christian Schwarz - 3 years, 6 months ago

Lol you would have to know the theorem beforehand to be able to solve the problem ... thankfully I counted / educated guessed and got the right answer that way.

Kyle Humphrey - 3 years, 6 months ago

Modifying the problem might make more sense too. Consider two similar cases. Case 1: first move is east. Case 2: first move is north. In case 1, We must completely eliminate the leftmost column (can't travel backwards) and the topmost row (if you travel to the topmost row, then you cut off all return paths). This leaves us with one less row and one less column, or a 4x2 grid. Then you can use the combinatorial method mentioned above (articulated by noting that it will take 6 units to reach the destination, and any two of them must be traveling north, so 6c2, or 15). So Case 1 gives 15 paths. Well, Case 2 is the same, so.... yeah

Jon Bushman - 3 years, 6 months ago

Did anyone notice the connection to Pascal's triangle? Take the number of squares in one direction (so in this case 3 or 5) then move that number along the edge of the triangle. Then take the other number of squares (so 3 or 5 here) and move that number along in parallel with the other edge and you'll get the answer for the path starting north (15 here). Multiply by 2 to get the full answer.

Chris Breederveld - 3 years, 6 months ago
Karen Hunt
Nov 19, 2017

Either the path from A must go up and be confined to the upper left 2x4 grid then go right to B (thus allowing a return trip along the right-most edge and then along the bottom), or it must go right and be confined to the lower right 2x4 grid, then go up to B (allowing a return trip along the top and then the left-most edge).

So for each case, there are (2+4 choose 4) = (6 choose 4) = 15 paths. Thus there are 15 + 15 = 30 paths in all.

Mustaf Ahmed
Nov 22, 2017

L a T e X LaTeX

There are two cases.

The path is started with the vector (1,0) and ends with the vector (0,1) The path is started with the vector (0,1) and ends with the vector (1,0) If this wasn't the case, you could not get back to A.

There are a total of 8 moves to get to the end for any valid path.

(1,0) _ _ _ _ _ _ (0,1) (0,1) _ _ _ _ _ _ (1,0)

There must be 5 Right movements and 3 Up movements.

For each case, 1 Right movement has already been selected and 1 Up movement has already been selected.

That leaves 4 Right movements and 2 Up movements for each case.

The missing 6 movements for each case comes down to permuting with repetition of 4 Right movements and 2 Up movements.

C(6,4) * C (2,2) for each path

2 * ( C(6,4) * C(2,2) ) = 30

Chew-Seong Cheong
Nov 24, 2017

We note that there will be no returnable path if the arrival direction to B is parallel to the starting direction at A . This is because at least the last arrival path to A would have been walked. Returnable paths exist when the starting direction at A is perpendicular to the arrival direction at B .

We also note that the grid of allowable to satisfy the condition is reduce by one column and one row to 4 × 2 4 \times 2 . And according to Rectangular Grid Walk , the total number of paths is given by ( 4 + 2 2 ) = 15 \binom {4+2}2 = 15 . Since there are two ways to start at A , the total number of such paths possible is 30 \boxed{30} .

We need to leave open one path from A to B open. Such will be going directly left and then up - on the border. That leaves that rectangle because our first move is decided. With the little 2x5 rectangle we have 15 possible paths. The answer is 15x2 because we can revert it.

Mohit Thakur
Nov 23, 2017

Consider a particular 2 path from sides of rectangle . As if any another path will be possible then that will also be possible.

Now grid is redused to 2×4 rectangle thus no. Of ways =15 as 2 such paths are possible 2×15=30 such paths fromA--B--A

It is eaaiest possible way..

Mohit Thakur - 3 years, 6 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...