I first read about Project Euler on Scott Hanselman’s blog.

After doing a couple of problems taken from the “easier” batch, just to not get frustrated right of the bat, I came across problem number 15 which I found intriguing.

This one is a good example of how hard stuff can be without a decent mathematical background. And that’s when frustration hit me big times.

Even though I finally figured out the correct answer, I cannot draw this particular problem to a close yet, as I am lacking a proper (implemented) algorithm. This blog post is a sum of what I know so far, including some failed attempts at solving the problem.

Failed attempt No. 1

I started with pen and paper, drawing a couple of 3×3 grids.

What I noticed by looking at the given example is that each path has a “mirror path”.

Starting at the top left corner of the grid you can either move to the right or downwards. Wether you choose to move right- or downwards, all subsequent steps can be mirrored as well.

Therefore it seems to be sufficient to determine all paths that start by a move to the right, and then simply double that number to get to the total number of paths.

My 3×3 grid experiment resulted in 20 possible paths from the top left corner to the bottom right. The first 10 paths are shown above, all starting with a step to the right.

I tried to derive an “algorithm” from the numbers I already knew.

1×1 grid –> 2 paths
2×2 grid –> 6 paths
3×3 grid –> 20 path
4×4 grid –> …

Guess what, I didn’t find one.

Also drawing a 4×4 grid already looked exhausting. And to make it to a 20×20 grid…the problem’s author must have chosen that number for a reason.

I was stuck.

Another failed attempt

I restarted with a 2×2 grid and assigned numbers to each point of the grid.

How many steps does ist take to get from the top left to the bottom right corner? Always four steps. E.g.  (1, 2) (2, 3) (3, 33) and (33, 333). Or (1, 11), (11, 22), (22, 222) and (222, 333).

Not all points in the grid are equal. From point 1 you have two choices (right or down). Point 3 only lets you move downwards. Point 333 is the bottom right corner from where you can go nowhere.

I fiddled with these ideas for a while…stuck again.

A more successful attempt

I had to look up the interwebs for a solution to this problem. But I wanted to avoid to…

• …accidentally uncover the correct answer without any further explanation.
• …copy a finished algorithm handed to me on a silver plate.

I just wanted to get pointed in the right direction.

These are the keywords that took me deeper down the rabbit hole:

• Binomial coefficient
• Pascal’s triangle

Looking at Wolfram MathWorld I knew I’d better start with Pascal’s triangle.

This is how Pascal’s triangle looks like.

Each number in the triangle is the sum of the two numbers directly above it.

Apparently the number of lattice paths through a grid are represented by the center column of Pascal’s triangle, the central binomial coefficient.

2 paths for a 1×1 grid, 6 paths for a 2×2 grid, 20 for a 3×3 grid and so on.

Here, the 2×2 grid written as Pascal’s triangle.

I consulted the On-Line Encyclopedia for central binomial coefficients and picked the 21st number, which was the correct solution to the problem.

This is the formula for the central binomial coefficient:

Now my task at hand is to figure this one out and to implement an algorithm.