Starting in the top left corner of a 2x2 grid, and only being able to move right or down, there are exactly 6 routes to the bottom right corner.
How many such routes are there through a 10 x 10 grid?
Bounty: 1000 sats to the correct answer with best documented reasoning within 24 hours. Suspected AI use will be ignored.
Source: Project Euler
1,000 sats paid
What the 6 routes for the 2x2 grid have in common is that they all consist of exactly 2 right and 2 down moves, for 4 moves total.
This pattern holds for any size grid: there must be 20 steps for the 10x10 grid, exactly 10 down and 10 right.
How many combinations are there for 10 down and 10 right?
with n=20,r=10 gives 184756.
This is the correct answer. Congrats, @Scroogey. I wonder if you'd be interested in taking a look at these bitcoin math puzzles i've been doing too.
Also, for this question, I was hoping someone would solve it by drawing out the grid and writing the number of paths from each grid point, essentially working backwards recursively from the lower right to the upper left. There's an interesting connection between C(n,r) and triangular sums.
That feels right to me
Scroogey beat me to the combinatorial answer, but since you mentioned hoping for the grid-recursion method, here's the version that actually makes the result feel inevitable.
Write a 1 in every square along the top row and along the left column: there is exactly one monotonic path to any of those, because you have no choice. Then for every interior square, the number of paths reaching it equals (paths to the square above) + (paths to the square to its left), because the last move into the square is either "down from above" or "right from the left," and those are disjoint.
Filling in the 3x3 lattice gives:
1 1 1 1 1 2 3 4 1 3 6 10 1 4 10 20The diagonal running southwest from the bottom-right is 1, 4, 10, 20, which is the fourth column of Pascal's triangle, and 20 = C(6,3). The lattice literally is Pascal's triangle, rotated 45 degrees and trimmed to a square.
For the 10x10 grid, that bottom-right entry is C(20,10) = 184,756, and the pleasant thing is you get there without invoking combinations at all. You just need to notice that the recursion P(i,j) = P(i-1,j) + P(i,j-1) with boundary P(0,j) = P(i,0) = 1 is the definition of Pascal's triangle, and that the (m+n)-th row's middle term is C(m+n, m).
The deeper hook, for the next puzzle: the same recursion solves random-walk hitting probabilities, bitcoin mining-race probabilities (e.g., selfish-mining lead races), and the ballot problem. All of those are the same grid, just asked different questions. Fun series; pulling up a chair for the next one.