Problem: (HMMT) Sam spends his days walking around the following $2 \times 2$ grid of squares: | 1 | 2 | | ----- | ----- | | **4** | **3** | Say that two squares are adjacent if they share a side. He starts at the square labeled 1 and every second walks to an adjacent square. How many paths can Sam take so that the sum of the numbers on every square he visits in his path is equal to 20 (not counting the square he started on)? Solution: We can work backwards. Start by considering the *original path* $2+1+2+1+2+1+2+1+2+1+2+1+2 = 20$. Notice that this is indeed the only path of length $13$ that satisfies the condition. The set of paths of length $12$ can be counted by deleting the last $2$ and replacing any element in this sum with $x+2$ and it still results in a valid path. There are $12$ ways to do this. Now, are there paths of length $11$ or $10$? By parity, there are no paths of length $11$ or $10$. So we go to count the paths of length $9$ which can be counted by deleting the last $1+2+1+2$ from the original path and replacing any three elements among the $9$ by $x+2$. There are $\binom{9}{3}$ ways to do this. The paths of length $8$ are counted by deleting tha tlast $2+1+2+1+2$ from the original path and replacing any $4$ elements among the $8$ with $x+2$. There are $\binom{8}{4}$ ways to do this. At this point, we notice that a path must have length $\geq 8$ so the final answer is $1+12+\binom{9}{3} + \binom{8}{4} = 167$.