0%

Problem 336


Problem 336


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.


最大最小安排

一架火车头被用来运输按如下顺序排列的四节车厢:ABCD。不过,有时候当火车头准备拉上车厢时,车厢并没有按照正确的顺序排列。
为了重新排列车厢,这些车厢被转运到了一个大型旋转台上。在某一个点将部分车厢分离,然后火车头带着分离点前的车厢离开旋转台,留在旋转台上的车厢随后旋转180度,然后再把所有车厢重新连起来。这个过程不断重复直到重排完成,不过我们希望尽可能少地使用旋转台。
有些安排,如ADCB,很容易进行重排:首先在A和D之间断开,然后DCB旋转180度,重新连接后就是正确的顺序。

然而,火车司机没头脑西蒙并不是一个有效率的人,他解决这个问题时,总是先把A车厢放到正确的位置,然后是B车厢,依此类推。

在有四节车厢时,西蒙所碰到的最差情况,我们也称为最大最小安排,将会是DACB和DBAC;这两种安排下,他都需要进行五次旋转(而在最有效的方法下,只需要三次旋转就可以解决)。西蒙解决DACB的过程如下所示。

可以验证,在有六节车厢时,共有24种最大最小安排,按字典序排列的第十个为DFAECB。

在有十一节车厢时,找出按字典序排列的第2011个最大最小安排。