|We have N rocks, labelled 1 through N, lined up on the river bank but not in the correct order.
We have a contract with Wally's Rock Permuting, Inc. (WRP): For the fixed price of 5 euros, WRP will accept a list of disjoint pairs of rocks, and transpose the rocks in each pair. For example, if he receives the list (3,5), (4,7), (1,8), and the rocks initially look like
10 6 8 5 2 3 1 4 7 9 |
after Wally leaves, they will look like
10 6 1 3 2 5 8 7 4 9
Blocks 3 and 5 have been interchanged, as have blocks 4 and 7, as have blocks 1 and 8.
WRP charged us 5 euros to do these three transpositions; he would also have charged 5 euros if we had requested only one transposition. But the pairs have to be disjoint: we cannot request (3,5), (5,4).
For a given N and a given initial order, suppose we plan our calls to WRP as efficiently as possible. For a fixed N, what is the most we should ever have to pay?
FYI: Although this problem may appear simple at first, the solution is actually fairly complex.
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the webmaster.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: firstname.lastname@example.org