Ponder This

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

to the order

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

(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:

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

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

One cycle is:

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

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)

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

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").

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:

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

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

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

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.