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.

(In reply to Answer by Old Original Oskar!)

You very quickly homed in on the Fibonacci "secret" of the problem, but you made one small slip: You cannot have L(0)=0 and still have L(2) have its correct value of 2.  L(n) is in fact F(n+1) where F(n) is the usual nth Fibonacci number such that F(0)=0 and F(1)=1. It makes some sense that L(0) be considered to equal 1 because there is a unique empty ladder satisfying the conditions.

Posted by Richard on 2004-09-28 18:52:51