IBM Ponder This #012 · April 1999

There are $N$ rocks labelled $1$ through $N$, lined up on a riverbank but not in the correct order.

For a fixed price of 5 euros, Wally's Rock Permuting, Inc. will accept a list of disjoint pairs of rocks and transpose the rocks in every listed pair. The price is the same whether the list contains one pair or many pairs, but no rock may appear in more than one pair in a single call.

For a given $N$ and initial order, suppose calls to WRP are planned as efficiently as possible. For that fixed $N$, what is the most that might ever have to be paid?

Solution

Best opened after a real attempt

Solution

To be added.