Behold the solution to Wright Challenge #3. If you forgot the actual question, click here to see it again.

Given that there are far too many combinations to count for a 40-step staircase, we can start by solving a smaller problem, and looking for a pattern.  For example, it is easy to see that there is 1 way for our Sally to climb a staircase with one step, and two ways to do one with two steps.  We write our findings below:

Every entry in the right-hand column seems to be the sum of the previous two.  We can verify without too much pain that there are 8 + 5 = 13 ways for Sally to climb 6 steps.  A handheld calculator can now verify that there are 165,580,141 ways for Sally to climb 40 steps.

It is possible to demonstrate that this pattern is correct.  Let's look at Sally at the bottom of 40 steps, deciding what to do.  She has a choice:  She can start by going up one, or she can start by going up two.  If she goes up one, she has 39 left to go, and if she goes up two, she has 38 left to go.  So the number of ways she can climb forty stairs, N(40) is equal to the number of ways she can climb 39, N(39) plus the number of ways she can climb 38, N(38).  We get the equation: 

N(40) = N(39) + N(38)

This reasoning holds regardless of the size of the staircase.  So the pattern we've noticed is always true.

The sequence {1, 2, 3, 5, 8, 13, 21, 33, 54, ... } is called a Fibonacci Sequence and comes up a lot in mathematics.  Doctor E once was given a homework assignment with ten different problems on it, all from different areas of life, and all of them turned out to wind up as Fibonacci sequences.  To learn more about Fibonacci sequences, click on Sally, and she will be happy to take you to a relevant web-site.

A different way to get to the correct answer was to use combinatorics directly.  She can take 40 one-steps.  (That's one way)  She can take 38 one-steps and 1 two-step.  (There are then ways to arrange them).  She can take 36 one-steps and 2 two-steps.  (There are then ways to arrange them).  So the total number of ways for Sally to climb the steps is , which a computer algebra package (or patient person) can add up to get 165,580,141.

Lots of heros and villians died in the Crisis on Infinite Earths.   Some of the big ones were the Flash (Barry Allen), Supergirl (Kara Zor-El), and the Earth-2 Lex Luthor.

You have just read the solution to the Wright Challenge #3.  Please feel free to email us your comments and feedback.  Why not try the current Wright Challenge now?

Web Page design: Doug Shaw