Problem 1 (Merry Christmas)

How many ways can you spell MERRY CHRISTMAS (ignore the space between the words) by moving to the right, left, or down in the following pyramid

Solution

If you take smaller pyramids, it is not hard to count the number of ways of spelling AT, CAT, and SCAT in the triangles

getting 3, 7, and 15 ways. You might see a pattern and suspect the number of ways of spelling an n letter word is 2n - 1. Thus, you might guess the number of ways of spelling MERRY CHRISTMAS is 214 - 1 = 16,383. To prove this is the correct number, we call

and show the relationship

Tn+1 = 2Tn + 1

To understand why this is true, look at the above leftmost triangle that spells AT (n = 2), and then look at the triangle to its right (n = 3) that spells CAT. Now, if you spell the word CAT backwards in the n = 3 triangle starting from the second to the last letter A, you see there are two backwards paths from all the A's to C's, with the exception of the A in the middle column, in which case there are three paths (one to the left, one to the right, and one up). Hence, we have the formula

Tn+1 = 2Tn + 1

You can see that this formula also holds for pyramids with more letters. In other words, every time you increase the number of letters in the pyramid by 1, you double the number of paths and add 1.
Knowing this simple relationship and using the fact that T1 = 1 (only one path for a one-letter word), we can simply compute the values of Tn for different values of n. Doing this, we get

We can also see that the equation Tn = 2n - 1 satisfies the difference equation Tn+1 = 2 Tn - 1 since

2n+1 - 1 = 2 (2n - 1) + 1

Hence, if we had a pyramid with 30 letters, the number of paths would be

T30 = 230 - 1 = 1,073,741,843

[Next] Problem 2 (Periodic Sequence Problem)
[Up] December Solutions
[Home] Home Page
[Mail] Send EMail to Maine Math Talent Search
[Contents] Maine Math Talent Search Contents

Last modified on Tuesday, January 12, 1999