All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Merit Review (Posted on 2004-09-28)
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.

 See The Solution Submitted by Richard Rating: 4.2857 (7 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 re: Answer | Comment 2 of 6 |

Amazing.

But since I have the following already written out, I'll include it:

Movement on the ladder can take place only in the interchange of pairs of adjacent employees.  If two adjacent employees would both go in the same direction, say up, then the person displaced by the top one, being is a now-smaller area of the ladder, would have to go down the ladder, but the position immediately below would be occupied by the lower of the two that are rising, so there would be no position for this displaced person.  And obviously if one person goes up and the person he is displacing can't also go up, the two must interchange.

The possibilities for a 20-person ladder are: leave everyone in the same position, interchange one pair, interchange 2 pairs, ..., interchange 10 pairs.

There's obviously one way to leave everyone unchanged.  Interchanging one pair can be done in C(19,1) ways as we need to select the position of one pair within 18 singlets (19 objects altogether). Two pair can be done in C(18,2); ... ; ten pair can be done in C(10,10) ways, as there are 10 pairs and no singlets.

The ways, in summary, where pairs are swapped and singles stay in place:

`pairs sngl  ways 0     20      1 1     19     19 2     18    153 3     17    680 4     16   1820 5     15   3003 6     14   3003 7     13   1716 8     12    495 9     11     5510     10      1`

for a total of 10946 ways.

In general, for n employees, the number of ways would be Sigma{i=0 to [n/2]} C(n-i,i), where the square brackets indicate the largest integer (floor) function.

Here's a table with some values for various n:

`  1       1  2       2  3       3  4       5  5       8  6      13  7      21  8      34  9      55 10      89 11     144 12     233 13     377 14     610 15     987 16    1597 17    2584 18    4181`

Can the boss examine all these 10,946 ways of rearranging the 20 employees?  The boss's most likely strategy is to determine which of the pair switches (if there are any) is the most important to make.  Let's say that is to switch persons 4 and 5. He then has two other groups to consider: persons 1-3 and 6-20.  As they have 3and 15 people respectively, the one has 3 ways of rearranging and the other has 987.  In all that's 3*987=2961.  By selecting this pair (4 and 5) to switch, the boss has narrowed the overall choices down from 10,946 to 2,961, in effect "considering" and eliminating 7,985 reorderings in one fell swoop, as they don't include his most important pairwise swap.

Similarly the 987 ways of breaking down that group of 15 that's left can be analyzed by starting with the most important swap (if any) in that group, and so forth.

So in that sense, yes, the boss can consider all the possible reorderings, even though the number seems formidable.

 Posted by Charlie on 2004-09-28 12:29:39

 Search: Search body:
Forums (0)