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!)
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 55
10 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 |
re: Answer
