Ernest is one of N (currently 20) engineers that make up the Advanced Projects Group. Each year the group is subjected to "merit review" where the group members are placed by their boss (not a member of the group) "on a ladder" by assigning each member to a unique rung of an N-rung ladder which will then determine the member's annual raise.
This year the group has exactly the same twenty members as last year and the boss has stated that he will obtain this year's 20-rung ladder from last year's 20-rung ladder in such a way that if a person's position is changed, it is not changed by more than one rung up or down.
Ernest questions whether the number of possible such ladders is small enough that every one of them can reasonably be considered by the boss. How many such are there, in fact? Generalize to groups of size N.
Let's call L(n) the number of ladders with n people. Consider the last person. If he stays in the last place, L(n)=L(n-1); otherwise, he must step up to the (n-1) place, and the person there must come down, so there are L(n-2) options remaining. Thus, L(n)=L(n-1)+L(n-2), with L(0)=0, L(1)=1, so the answer is the Fibonacci sequence.
P.S.: As Richard noted, L(2)=2, so we need L(0)=1, and the answer still is the Fibonacci sequence, but with the first term removed. Thanks, Richard!
Edited on September 29, 2004, 6:02 am
Answer
