Maximix Arrangements

A train is used to transport four carriages in the order: ABCD. However, sometimes when the train arrives to collect the carriages they are not in the correct order.
To rearrange the carriages they are all shunted on to a large rotating turntable. After the carriages are uncoupled at a specific point the train moves off the turntable pulling the carriages still attached with it. The remaining carriages are rotated 180 degrees. All of the carriages are then rejoined and this process is repeated as often as necessary in order to obtain the least number of uses of the turntable.
Some arrangements, such as ADCB, can be solved easily: the carriages are separated between A and D, and after DCB are rotated the correct order has been achieved.
However, Simple Simon, the train driver, is not known for his efficiency, so he always solves the problem by initially getting carriage A in the correct place, then carriage B, and so on.
Using four carriages, the worst possible arrangements for Simon, which we shall call maximix arrangements, are DACB and DBAC; each requiring him five rotations (although, using the most efficient approach, they could be solved using just three rotations). The process he uses for DACB is shown below.

It can be verified that there are 24 maximix arrangements for six carriages, of which the tenth lexicographic maximix arrangement is DFAECB.
Find the 2011th lexicographic maximix arrangement for eleven carriages.

This is a combinatorial problem that involves working with permutation phrases. “Lexicographic” relates to alphabetical order, and “maximix” relates to the maximum number of rotations. There are eleven carriages, so we must work with the set {A,B,C,D,E,F,G,H,I,J,K}.

The least efficient form of sorting would be to handle the carriages one at a time, starting from A and coming to K in order. We can notice that the maximum number of moves is achieved when the carriages are arranged in such a way that each carriage (from B onward) has the next one in alphabetical order located to its left.

For example, if we have three carriages ABC, the maximix arrangement would be BAC – B has A to its left and C has B to its left. To sort this arrangement using Simon’s method would require 3 moves.

If we have four carriages, the maximix arrangements would be BACD, CBAD, CBDA, DCBA – in each case, aside from the first carriage, each railway car has the one following it in alphabetical order to the left of it. Some thinking and trying will show that each of these requires 5 rotations to sort.

Now coming to the problem, we want the 2011th lexicographic maximix arrangement for eleven carriages.

We first note that the lexicographically first maximix arrangement of 11 carriages is BACDEFGHIJK, which we’ll call the reference arrangement. We notice that all arrangements with B being the first carriage constitute of 10! = 3,628,800 lexicographic arrangements, since the rest 10 carriages can be arranged in any of the 10! ways.

However, among these 10!, only a fraction will be maximix. They are those which follows the rule that, except for the first carriage, a carriage has the next one alphabetically to the left of it. These arrangements would be in the form like BAC…., BADC…, BADCE…, and so on till BADCFEHGIJK. Each form will contribute (n-2)! arrangements where n is the number of letters. For example, BAC… will have 9!, BADC will have 8!, and so on.

Summing these up we have a geometric sum => 9! + 8! + 7! + … + 0! = 3,628,799 which is just less than 2011. This means, all these arrangements will not achieve 2011th lexicographic maximix arrangement and we need to move to the next carriage i.e., C.

For C being the first carriage, the lexicographically first maximix arrangement of 11 carriages is CBADEFGHIJK. Similarly like before, we sum up the respective factorials to find out if we reach or cross 2011. But again we fail to touch 2011 even after summing all possible maximix arrangements beginning with C.

Next, we move on with D being the first carriage. The lexicographically first maximix arrangement now is DCBAEFGHIJK. Summing all possible maximix arrangements starting with D (i.e., DCBA…, DCBEA…, DCBEFA…, etc), we get 3,628,799.

We still haven’t touched 2011. However, we do know our 2011th arrangement does come after all maximix arrangements starting with B,C and D. Therefore, our first carriage will be E.

From here, it is simply a matter of subtraction and deduction as we have narrowed down the range. We need to find out which carriage comes next after E.

We first try EFBA…. But EFBA… series has (8!) + (7!) + …. +(1!) = 403,199 lexicographical maximix arrangements which is much more than what we want. This means, the carriage next to E is not F.

Let’s try EGBA…. . The EGBA… series has (7!) + (6!)+….+(1!) = 51,999 arrangements. This is still more than what we want.

We move to EHBA… . The EHBA… series has (6!) + (5!)+….+(1!) = 8,639 arrangements. This is still more than what we want.

Moving ahead to EIBA…. . The EIBA… series has (5!) + (4!)+….+(1!) = 1,564 arrangements. This is less than 2011. This means that the second carriage after E cannot be I, but it must be H (as we have proved it cannot be F or G).

With EH as the first two carriages, our lexicographic counter is at 403,199 (B starting arrangements) + 403,199 (C starting arrangements) + 403,199 (D starting arrangements) + 1 (Order E starts with) + 50,400 (E starts with F arrangement) + 8,100 (E starts with G arrangement) + 1,209 (E starts with H arrangement) = 1,266,108.

Subtracting this from 2011,
2011 – 1,266,108 = 744,903.
So, we are looking for the 744,903rd lexicographic maximix arrangement in the EH starting arrangements.

Continuing in the same vein, we find the remaining carriages.

When J is the third carriage, EHAJ.. . series has (4!) + (3!)+….+(1!) = 288 arrangements. Clearly, J cannot be the third carriage since 288 is less than 744,903.

When K is the third carriage, EHKJ.. . series has (4!) + (3!)+….+(1!) = 288 arrangements. Clearly, K cannot be the third carriage since 288 is less than 744,903.

So the third carriage is I.

Continuing on, we find that the subsequent carriages are J, K, F, B, A, G, C and D.

So the 2011st lexicographic maximix arrangement for 11 carriages is EHIJKFBAGCD.

More Answers: