Ponder This Challenge - April 1999 - Wally's Rock Permuting (WRP)

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

Solution

• Click here to view the solution

  10 euros, regardless of N, with exceptions for very small N, namely 0 if N=1, and 5 euros if N=2. We can always achieve the desired permutation with only two calls to WRP.

  Suppose first that we want to go from the order

  1   2   3   4   5   6   7

  to the order

  7   1   2   3   4   5   6.

  We need to achieve a permutation known as a "cycle": block 1 needs to go where block 7 is now, block 7 to where block 6 is, etc., and finally block 2 to here block 1 is now. On the first call to Wally, interchange blocks m and 7+1-m, for each m=1,2,3, so that we will give Wally the list

  (1,7), (2,6), (3,5).

  (For k blocks, this is either (k-1)/2 or k/2 pairs, depending on whether k is even or odd.) After his first visit, Wally will leave us with:

  7   6   5   4   3   2   1.

  Now give Wally the pairs (m,7-m) for each m=1,2,3, namely the list (1,6), (2,5), (3,4) so we end up with

  7   1   2   3   4   5   6.

  (This time it's either (k-1)/2 or k/2 pairs.) Each permutation can be broken into disjoint cycles, and each cycle can be solved in two steps in this manner. Because the cycles are disjoint, we can do all the first steps simultaneously, and all the second steps simultaneously. Let's do the initial permutation given in the problem, which was generated at random.

  10   6   8   5   2   3   1   4   7   9

  One cycle is:

  10 -> 9 -> 7 -> 1 -> 10.

  That is, block 10 moves to where 9 is now, block 9 moves to where 7 is now, block 7 moves to where 1 is now, finally closing the cycle with block 1 moving to where 10 is now.

  The second cycle is

  6 -> 3 -> 8 -> 4 -> 5 -> 2 -> 6.

  The first cycle involves two steps: First step: (10,1), (9,7) Second step: (10,7) The second cycle also involves two steps: First step: (6,2), (3,5), (8,4) Second step: (6,5), (3,4) Doing the steps in parallel: First step: (10,1), (9,7), (6,2), (3,5), (8,4) Second step: (10,7), (6,5), (3,4)

  10   6   8   5   2   3   1   4   7   9    initial order  1   2   4   3   6   5  10   8   9   7    after first step  1   2   3   4   5   6   7   8   9  10    after second step

  This method will always work.

  Another method (which also costs at most 10 euros), which is easier to do but tricker to prove correct, is as follows. Write three rows, the first being the initial ordering, the third being the final ordering, and the second being the (yet unknown) intermediate permutation (after WRP's first visit).

  10   6   8   5   2   3   1   4   7   9    initial order  x   x   x   x   x   x   x   x   x   x    after first step  1   2   3   4   5   6   7   8   9  10    after second step

  Take the first unknown element (the one underneath "10") and demand that it be left alone during the first permutation, (in this case it remained "10").

  10   6   8   5   2   3   1   4   7   9    initial order 10   x   x   x   x   x   x   x   x   x    after first step  1   2   3   4   5   6   7   8   9  10    after second step

  During the second round of transpositions, since 10 went to 1, we must have 1 going to 10, so that we can fill in the element above 10:

  10   6   8   5   2   3   1   4   7   9    initial order 10   x   x   x   x   x   x   x   x   1    after first step  1   2   3   4   5   6   7   8   9  10    after second step

  So the first permutation sent 9 to 1, and must send 1 to 9:

  10   6   8   5   2   3   1   4   7   9    initial order 10   x   x   x   x   x   9   x   x   1    after first step  1   2   3   4   5   6   7   8   9  10    after second step

  The second sent 9 to 7 and so must send 7 to 9:

  10   6   8   5   2   3   1   4   7   9    initial order 10   x   x   x   x   x   9   x   7   1    after first step  1   2   3   4   5   6   7   8   9  10    after second step

  Now we can gain no new information, because the first permutation left 7 alone. We have done the first cycle. So we go back and again pick the first unknown element (the one under 6), demand that it be left alone in the first step, and go back and forth to pick up information on the next cycle. Skipping intermediate steps, we come up with

  10   6   8   5   2   3   1   4   7   9    initial order 10   6   5   8   3   2   9   4   7   1    after first step  1   2   3   4   5   6   7   8   9  10    after second step

  We are done, because this particular permutation was the product of only two cycles. Notice that this solution is as good as the other one (still costing only 10 euros) but is not the same solution.