The 15th problem in Project Euler.
Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner. How many routes are there through a 2020 grid?
Mmm… walk in the grid; it sounds like a problem of graph theory. I’m sure there must be some complicated solution for this. But I’m gonna solve it with the simplest way. To define “pass by one grid in either direction” as one step. Without going back, one needs to 20 steps leftwards and 20 steps downwards to travel from the top left corner to the down right corner. The problem turns to “how many combinations of leftwards steps with downwards steps”, which is a simple combination problem in mathematics. Thus, the answer is C(20, 40) .
result <- choose(40, 20) cat("The result is:", result, "\n")