Fall 2008 Problem 3: C-E-N-T-E-N-A-R-Y
You want to spell Centenary using the picture below. You start at the letter C and then move either straight down to the E below or to the E below and one letter to the right. At every letter you repeat this process: you either move straight down or move down and to the right. (So, for example, from the second N on the third row, you can move to the second T on the fourth row or the third T on the fourth row.) You never move up or to the left.
Following this procedure, in how many different ways can you spell CENTENARY?
Solution
Our first correct solution came from Matthew Chumley, earning him three points. Brent Krise also had the best explanation (see below), earning him 3 points.
There are 256 different ways to spell CENTENARY in this fashion. To figure this problem out, I started with a smaller word. I used a three letter word and found 4 different ways to spell it. Then I moved to a four letter word and found there were 8 different ways to spell it. It seemed that a pattern was occurring where the number of different ways, P(n) was equal to 2^(n-1), where n was the length of the word. To assure my assumption was correct I proved it by induction. The base case when n=1 is simple, there is only 1 way. Now for the inductive step, assume P(n)=2^(n-1) and show P(n+1) = 2^(n+1-1) = 2^(n). We know that P(n+1) can be rewritten as P(n)*2 since we are just doubling the ways from n to n+1. Then subbing P(n)=2^(n-1) we get 2*(n-1)*2 = 2^n. Thus the number of ways to spell CENTENARY is 2^(9-1) = 256.
Other correct solutions (earning three points) came from Sterling Williams and Michaela Berg. Correct solutions from non-Centenary students came from Mark Goadrich, Scott Jackson, and Chris Evert.