Introduction
Project Euler is a websites dedicated to problem solving. The site is is similar but much older than the usually more known website called HackerRank. Problems at Project Euler always require a number as an answer. The problems increase in difficulty. Most problems can not be brute forced (at least not in the early 2000s) and therefore often requires a mathematical trick to quickly find the answer. Below are a couple of selected problems which sparked my interest, as they are easy to understand and have an elegant solution.
Problem 15
Answer is: 137846528820
Converting the original problem statement to finding all sequences of Downs (D) & Rights (R), makes the problem easier to solve. In the given example, one has 2 Downs and 2 Rights. Arranging them in all possible permutations as in the figures gives the following 6 sequences
R1 R2 D1 D2
R1 D1 R2 D2
R1 D1 D2 R2
D1 R1 R2 D2
D1 R1 D1 R2
D1 D2 R1 R1
Now the trick is to spot how this relates to factorials. In the example above, there is a total of 4 moves for all permutations. All possible arrangements of these 4 moves results in 4! or 24 possible moves. However, the key insight is noticing, that is does not matter which Down of the 2 Downs we pick, neither which Right of the 2 Rights we pick. This means that we must remove all duplicate arrangements such as D1 D2 R1 R2 and D2 D1 R1 R2, as they are equal based on the problem statement. We can therefore divide the total number of arrangements, first with the number of Down arrangements and then again with the number of Right arrangements.
( (Downs + Rights)! / Downs!) / Rights!
Putting this into play with the 2×2 example from the beginning
(4! / 2!) / 2! = (24 / 2) / 2 = 6
And for a 20×20 grid the answer becomes
137846528820