Grind Report 15

Problem 15

Starting in the top left corner of a 2x2 grid, there are 6 routes (without backtracking) to the bottom right corner.

[2x2 grid routes]

How many routes are there through a 20x20 grid?

*WARNING: This contains the solution!*

This was an interesting and challenging problem! That is if you don't have any background with this type of problem. To be completely honest, this was the first problem thus far that actually had me stumped. I enjoyed it!

My initial intuition was that there must be some type of equation that represents the answer. The grounding for this thought was based on the fact that the number of routes grows with the size of the grid. But how? This question daunted me for nearly an hour before I came to the conclusion that I would not be able to derive this algorithm and there must be another way. Before I move on though, I would like to share some of my attempts.

For some reason, along with my initial intuition came the factorial sign (!) and so I played around with that some. I saw that for the 2x2 grid 3! = 6 which is (2 + 1)!. I needed more samples to work with so I figured out that 1x1 = 2 and 3x3 = 20. (1 + 1)! = 2. I was really onto something! (3 + 1)! = 24 ...or not >.<.

My next attempt was nxn = (2n)! / 2n. 2x2 = 4! / 4 = 6. Good... 6! / 6 = 120...not quite. I played around with some other numbers but soon moved onto my next method.

This other method consisted of me staring at all the possible 3x3 routes and trying to come up with some sort of elegant way to calculate the number of paths for any nxn grid. I tried many things like sorting the routes by the number of turns they took, breaking the 3x3 into a 2x2 and seeing if I could build off of the previous nxn grid...ect. Some of these ideas where definitely better than others, but in the end I had come up with nothing. I was for once actually stumped.

So I turned to my good friend, Google, and asked him what he knew about this problem. I was looking for some type of hint - a push towards the solution. Well, he told me exactly what I was asking for...and way more. Unfortunately, while I was attempting to find a hint, I found a HUGE hint that led to the solution in about...3 seconds...

What I found was that this problem is strongly connected with pascal's triangle and by drawing the triangle inside the grid (with the outside 1's on the outside of the grid) you can actual find the number of possible routes every time by looking at the largest number (it will be in the corner). If you do this starting from the bottom corner of the grid up to the start corner each number inside of the grid represents the possible number of routes from that corner. You have no idea how close I was to figuring this out. I went ahead and programmed something along these lines to get the solution.

#include <string>
#include <iostream>

using namespace std;

const int diminsion = 20;

int main()
{
int total;
//this grid will be a pascals triangle
long long grid[diminsion + 1][diminsion + 1];
//fill in the sides with 1
for (int i = 0; i < diminsion + 1; ++i)
{
 grid[0][i] = 1;
 grid[i][0] = 1;
}
//fill in the middle
for (int i = 1; i < diminsion + 1; ++i)
{
 for (int j = 1; j < diminsion + 1; ++j)
 {
  grid[i][j] = grid[i - 1][j] + grid[i][j - 1];
 }
}
cout << grid[20][20];
}

After getting the solution I was able to read the forums for this question and see what the different solutions people had come up with. Apparently there is another way to solve this problem. This other method deals with combinatorics, which I almost took last semester but didn't because I wanted to take Linear Programming. I don't know all of the details that go into finding this solution but I do know what the solution looks like.

(40!) / (20! * 20!)
((2n)!) / (n! * n!)

...seriously!? >.>;

*saved game*