IBM Research | Ponder This | April 1999 challenges
Skip to main content

Ponder This

April 1999

<<March April May>>


Ponder This Challenge:

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: webmster@us.ibm.com

  

Challenge: 04/01/99 @ 12:00 AM EST
Solution: 05/01/99 @ 12:00 AM EST
List Updated: 05/01/99 @ 12:00 AM EST

People who answered correctly:


Attention: If your name is posted here and you wish it removed please send email to the webmaster.