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 ponder@il.ibm.com.

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