Last November I have solved Problem 15 of Project Euler (a counting problem involving paths in square grids), and, although the problem admits a simple solution, some of the solutions presented in their forums are very complicated. Thus, I thought it would be a good idea to present my solution, as I consider it very simple.
Problem statement
Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.
How many routes are there through a 20×20 grid?
My solution
In order to make the problem more interesting, let us investigate the more general problem of counting the number of routes in a n×n grid. Our argument is based on three observations:
- all the paths have size 2×n (the reason is obvious: you have to go right n positions and down another n positions);
- since we can only go right or down, we can identify every path by a string of Rs and Ds, where a R means going right and a D means going down; as an example, the paths illustrated in the problem statement are (from left to right and from top to bottom): RRDD, RDRD, RDDR, DRRD, DRDR and DDRR;
- the strings mentioned above must contain the same number of Rs and Ds.
From these three observations, we can transform the problem to the following:
How many different strings of size 2×n, consisting of n Rs and n Ds, there are?
The solution is now very simple, because the positioning of n Ds (or Rs) determines the positioning of the other n Rs (or Ds). Hence, the number we are interested in is the number in which we can choose n positions from 2×n available. The answer, using the traditional notation for the binomial coefficient, is:
Instantiating n with 20, we get the answer to the initial problem of the 20×20 grid.
Generalization to m×n grids
The generalization to a m×n grid is also simple. The only difference is that the strings have length m+n. Using the same reasoning as above, the number of paths through a m×n grid is:
Final note: If you want to access the forum of the problem, you have to solve it.
10 Comments
Funny - I searched for “paths through a square grid” in trying to solve the very same problem on the very same site.
Thank you for a clear explanation.
Hi Fish613,
I’m glad you find the explanation clear. Thanks for your comment.
You’re very welcome
I’m currently trying to make my own solution work, also involving the binomial, but my program fails to give the right answer, even though I’m sure it’s working properly
As long as you define the factorial function correctly, it should be very easy. In Haskell, for instance, you can define it as:
fac 0 = 1
fac n = n * fac (n-1)
Good luck!
How many routes is there on a 4 by 4 grid?
Boo2468: 70 ?
useful for Google Treasure Hunt 2008 at http://treasurehunt.appspot.com/ … Thanks !
Dr. Goulu: no problem! Good luck with Google’s challenge.
hey!
how many solutions would be in a 8X8?
=D
Amanda,
just replace n by 8 in the first formula and you get the desired result
2 Trackbacks/Pingbacks
[...] pour un damier de 56×32 cases (le nombre change pour chaque participant) et dans ce cas, la réponse est 232059241971866600926656. Ca suppose donc déjà de disposer d’une bonne calculatrice [...]
[...] gets solved just searching in Google for “grid path right down” from there you will get the equation that you must run on any language that has Big Integer implementations, since involves the [...]
Post a Comment