Problem 15 is brilliant in its simplicity. Let’s take a look at the description.
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.
How many such routes are there through a 20×20 grid?
There are many ways to solve this problem, but these could be computationally intensive. But if we take a step back, we will realize the underlying math, which then makes it trivial.
Start with a 1×1 grid. The only allowed moves are right and down. To get from the top-left corner to the bottom-right corner, we will have to make two moves, exactly one in each allowed direction.
Next, consider a 2×2 grid. In this case, we will have to make four moves, exactly two in each direction. The order in which we make these moves does not matter. This is the same as picking two people from a group of four. We can choose the first person in 4 ways and the second person in 3 ways. But since the order is irrelevant, we can choose the two persons in 2 ways, for a total of 4 x 3 / 2 = 6 ways. This is the definition of combination, and the formula for this is given as
Applying this to our 20×20 grid, we will have to make 40 moves, exactly 20 of which are to the right, and the rest are down, and the order of these moves does not matter. If we are bold, we can work this out on paper, or we can let a computer do the work for us.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
# In a 2 x 2 grid, to get from the top-left to the bottom-right, # we have to make 2 moves down and 2 moves right for a total of 4 moves # The order of making these moves does not matter. # We can make 4 moves in 4! ways. We can make the two moves in 2! ways # So the total number of ways is 4! / (2! * 2!) # Which the formula for nCr, which is n! / (r! * (n-r)!) # We will whip up a quick function to compute factorials and use it def factorial(n): product = 1 for i in range(2, n+1): product *= i return product print(factorial(40) // (factorial(20)**2)) |