IBM Research | Ponder This | April 1999 solutions

# Ponder This

## April 1999

<<March April May>>

 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 where 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.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com