How many paths in the figure below can you find that spell ‘MISERABLE’? Your paths may begin at any 'M' and take steps horizontally (left or right) and down.
Solution
The answer is . Why? Here is one explanation.
Let’s build the MISERABLE pyramid from the bottom up (top down is also possible). With only the final E, there is only one path. Add the Ls around that E as in the figure, part (I) and there are 3 paths. Add the Bs as in the figure, part (II) and there are now 7 paths.
We seem to be faced with the series 1, 3, 7, 15, . . . which consists of powers of 2 minus 1. That, in turn, suggests that for the whole tower of MISERABLE (9 letters), the number of paths is the ninth power of 2 minus one, or 511, as announced above.
To cement this explanation, consider the last step. Suppose that the 8 letter pyramid, as in the figure part (III) under the diagonal lines, has, as we believe, paths. When we add the Ms then every path in the resulting 9-letter pyramid begins with an M and then enters the 8-letter pyramid and follows one of the paths of length lying entirely within that sub-pyramid. The crucial question is: How many times does each of those paths get used?
If you look at the full pyramid, the whole of figure part (III), you will see that each I is adjacent to 2 M's except the top I which is adjacent to 3 M's. That means the number of paths in the full pyramid is the twice the number of paths of length 8 plus three which in turn is
