Google treasure hunt
Google australia is holding a brain teasing treasure hunt. The first question looks like this:
A robot is located at the top-left corner of a 53 x 32 grid1. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. How many possible unique paths are there?
The first thing I thought about was calculating all the paths using dynamic programming and memoization:
Let P(w,h) be the number of paths the robot can take to go from to top left corner of an w x h grid to its bottom left corner. If the robot goes left, it has P(w-1, h) possible paths left, and if it goes down, it has P(w, h-1). Of course, P(w, 1) = P(1, h) = 1.
The second approach gives the same results, but is obtained in a completely different manner. In the first case, it's mainly algorithmic, whereas the second case is purely combinatorics and — I think — far more elegant.
In order for the robot to go from the top left corner of an w x h grid to its bottom left corner, it must go (w-1) times left, and (h-1) times down, which is a total of w+h-2 movements. The number of paths is then the number of way of choosing which of those movements are (for example) going left. That is, choosing w-1 elements out of a set of w+h-2, best known as the binomial coefficient C(w+h-2, w-1). Of course, to compute it, one would use the recurrence used in Pascal's triangle : C(n, k) = C(n-1, k) + C(n-1, k-1), with C(n,0) = 1 and C(0,k) = 0.
The really nice thing about this is that two different ideas lead to one same result (it's just a question of rewriting the recurrence). This is creativity 
Just to give you an idea of the numbers involved here : on a 67×51 grid, there are 2049503709637561751443717895527866 paths. Believe me: it's huge !
- the size of the grid is variable [↩]