|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 email@example.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: firstname.lastname@example.org