Euler Problem 15 – Lattice Paths

Lattice paths

Problem 15

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

PE15

How many such routes are there through a 20×20 grid

This has to be the toughest one till now. There are two types of difficult questions. One which you don’t understand at all what to do, I mean they are way out of your reach. There are other questions which you understand but then get quite stuck at it. This question was of second type.
As soon as I read it, I was sure that I don’t have to get into the graphical complexities of it and just consider this as a matrix, give them numbers and make an algorithm which will tell how you reach from point A to point B. So for 2 by 2 matrix , I made :

                  
                         1 -- 2 -- 3
                         |    |    |
                         4 -- 5 -- 6
                         |    |    |
                         7 -- 8 -- 9

So for this 2 by 2 matrix, there are 6 possible paths (as given in the question) which goes from point 1 to point 9. So there was the first generalization. For a n X n matrix there are going to be (n+1) * (n+1) points.
Now one way to solve this is writing down all the possible paths which it can take from first point to last point. So for this 2 by 2 matrix , all the possible paths are :

1 -> 2 -> 3 -> 6 -> 9
1 -> 2 -> 5 -> 6 -> 9
1 -> 2 -> 5-> 8 -> 9
1 -> 4 -> 5 -> 6 -> 9
1 -> 4 -> 5 -> 8 -> 9
1 -> 4 -> 7 -> 8 -> 9

Few observations :
• For a n X n matrix each path would contain 2n + 1 elements.
• There has to be n rights and n downs always to reach to the destination.

I was sure now, that there is formula to calculate the number of possible paths but it was difficult to arrive to the formula based only on this single matrix. So I decided to follow the same procedure for 3 by 3 matrix as well.
3 X 3 matrix also satisfied the above two observations and the number of possible paths for 3 X 3 matrix came out to be 20. It was not possible to find all the possible paths manually for 20 X 20. So I was trying to find out the formula for number of paths.

Matrix Paths
2 X 2       6
3 X 3      20

I was thinking about different kinds of generalization like 3 X 2 is 6 and 4 X 5 is 20. Ummm, but that doesn’t make any sense.

Maybe the number of paths in 3 X 3 matrix is 24 and I have missed some of them. So for n X n matrix we can have n + 1 ! paths. So for 2 X 2 is 3! And 3 X 3 is 4! . So when I checked with 21! as answer it showed as wrong answer and hence unfortunately my assumption was wrong. 3 X 3 only has 20 paths and not 24.
I thought about this for 3-4 days in various ways but finally I gave up and googled for a possible solution. As I correctly thought there was a formula to calculate but the formula was a little complicated for me to derive.

The formula was :
(2 X n) ! / n! n!

So for 2 X 2 matrix the answer is :
(2 X 2) ! / 2! 2! = 6

for 3 X 3 matrix it is :
(2 X 3)! / 3! 3! = 20

So finally, I just did the calculation in R 😛

prod(seq(40)) / (prod(seq(20)) * prod(seq(20)))
# [1] 137846528820
Advertisements

One thought on “Euler Problem 15 – Lattice Paths

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s