Project Euler/15

Project Euler problem 15 gives a square lattice, 20 x 20, and shows a shortest path through the lattice - one that follows the edges of the lattice. The question, then, is how many variations on this shortest path are possible?

I solved this question using Wolfram Alpha - as with many combinatorics problems, it turns out you don't need to generate all of the variations, you can write a closed-form expression for the number of combinations instead.

To derive the expression, we can think about the shortest path in a step-by-step fashion. We know that, ultimately, we are constrained to 20 down steps and 20 right steps.

If we examine the starting position, and how we are going to move, we know we have to take one right step in the first column. Once we do that, we will be on the second line of the lattice, and we will have 19 right-steps left. And so on.

But we can take as many down steps as we would like at each point - in fact, we could use up all 20 of our down steps before we ever take one step right. Or, we could use them all up right after we take one step right. Or we could use them all up after we take 20 steps to the right.

File:Euler15 Lattice1.png

File:Euler15 Lattice2.png