1. Here is a solution that requires only five swaps for
9 8 7 1 4 3 5 6 2 (1,9): 2 8 7 1 4 3 5 6 9 (2,7): 2 5 7 1 4 3 8 6 9 (2,4): 2 1 7 5 4 3 8 6 9 (3,8): 2 1 6 5 4 3 8 7 9 (3,6): 2 1 3 5 4 6 8 7 9
2. For this initial configuration
3 5 6 7 8 1 9 2 4
six swaps are sufficient. Here is one method to put it into a 1-away configuration:
3 5 6 7 8 1 9 2 4 (5,9): 3 5 6 7 4 1 9 2 8 (The 4 and 8 are now close enough.) (1,3): 6 5 3 7 4 1 9 2 8 (1,6): 1 5 3 7 4 6 9 2 8 (The 4, 8, 1, 3 and 6 are now close enough) (2,4): 1 7 3 5 4 6 2 9 8 (7,8): 1 7 3 5 4 6 2 9 8 (2,7): 1 2 3 5 4 6 7 9 8 Can you do better?
On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
3. Here is a very bad initial configuration for nine items:
8 9 1 2 3 4 5 6 7.
Each element is two away from its correct position. Each swap can do no better than moving a single sculpture into its correct position. Yet once the first seven sculptures are in place, the last two will be only one away, so seven moves is the worst case.
4. Omniheurist Tom Rokicki came up with the following beautiful solution (my colleague Richard Cole and mathematician Ivan Rezanka had similar intuitions).
One maximally bad initial configuration when the goal is to achieve a d-away configuration is to start with a d+1 rotation from the in-order configuration. For example, when d = 1, the configuration
8 9 1 2 3 4 5 6 7 is a 2-rotation. By contrast a 6-rotation (useful for to maximize the number of swaps when the goal is to achieve a 5-away configuration) on 9 elements yields:
4 5 6 7 8 9 1 2 3
Rokicki observed that there will be n-(d+1) numbers that are at least d+1 out of place (1, 2, 3 in the 6-rotation example), all in the same direction. Each swap can move only a single one of those numbers into range of its location.
Swapping them into place in order (for this example, swapping the 1 at position 7 with the 4 at position 1, then the 2 at position 8 with the 5 at position 2, and so on) is in fact an optimal solution.
In fact, no matter which initial configuration one starts with, one can swap 1 into place, then 2, then 3, and so on up to the largest d+1 sculptures. Those last ones are no more than d away from their proper places.
5. How many 1-away configurations are there for n elements?
Recall the Fibbonaci sequence that seems to come up in so much of mathematics:
1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Each number is the sum of the two previous ones, i.e., fib(k+2) = fib(k+1) + fib(k). Let's identify the numbers by their position in that list, so fib(0) = fib(1) = 1, fib(6) = 13 (remember we're starting from 0), and so on.
Well, the number of 1-away arrangements (including the perfectly sorted one) of n elements is just fib(n).
For n = 1, there is clearly just one (fib(1)).
For n = 2, there are two: 1 2 and 2 1.
For n = 3, there are three: 1 2 3; 1 3 2; 2 1 3
For n = 4, there are five: three that involve 2 3 4 with 1 fixed; then swap the 1 and 2 and there are two arrangements of 3 and 4.
In general, there are fib(n-1) permutations of length n with the first sculpture in place. If the first sculpture is not in place it must be at position 2, but this means the second sculpture must be in position 1 (no other element can be in position 1). So this fixes the first two positions out of order. Now there are there are fib(n-2) permutations of the last n-2 sculptures.
This last result was first discovered in the following nicely written article (in French) that you can find on the web:
"Quelques resultats dans la metrique des permutations,"by Rene Lagrange, Annales scientifiques de l'E.N.S. third series, tome 79, no 3, 1962, pp. 199-241.
http://archive.numdam.org/article/ASENS_1962_3_79_3_199_0.pdf
