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 re(3): Answer by Federico Kereki)

Yes! I had pretty much forgotten that one even though I did post a solution. But putting Charlie and Old Original Oskar! together gives a proof by counting only. One does need to figure out Charlie's doublet/singlet method of counting which requires some effort to justify. Counting (aka combinatorial or bijective) proofs, though, are more highly prized by the combinatorics crowd than are algebraic proofs.

Edited on September 29, 2004, 10:49 pm

Posted by Richard on 2004-09-29 15:50:19