April 1999
| 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.