The Muscle Moving Company has a bunch of heavy sculptures it wants to put in ascending order, from west to east, based on weight. However, it is not necessary to put them in precise order provided each sculpture is close to where it should be. Consider an ordering to be "k-away" if every sculpture is either in the place it should occupy according to its weight or at most in k places away from that position.
For example consider the figure
The sculpture whose weight is 9 tons is in the 9th position and the sculpture weighing 7 tons is in the 8th position so only one away from where it should be. Every other sculpture is at least two away from where it should be if the sculptures were perfectly sorted. To rectify this, Muscle swaps sculptures. For example, suppose Muscle could swap the sculpture at position 1 with the sculpture at position 4, denoting the swap as (1,4). Then Muscle could swap the sculpture at position 2 with the sculpture at position 6 (i.e. (2,6)).
This yields
Finally, (3,5) and (5,7) yields a 1-away design:
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.
In this example, Muscle got a free ride, in that two sculptures started out being at or near enough to their right places.
1. Here is a slightly harder one:
Could you help Muscle with this rearrangement? There is a method to achieve a 1-away design using only five swaps. But there may be better methods. Please give it a try.
2. Here is another initial configuration:
3 5 6 7 8 1 9 2 4
How many moves does this require to achieve the 1-away design? (Hint: I think this one is harder.)
3. Muscle wants to know the maximum number of swaps that might be necessary for nine sculptures to achieve an ascending 1-away ordering from west to east. Can you find an arrangement of 9 distinct numbers such that the number of swaps required to achieve a 1-away ordering is maximized? (Hint: Note that we are asking a "maximin" question: which initial configuration requires the maximum number of swaps assuming that you can find the best (minimal) strategy for that configuration?)
4. Clearly, if you have n numbers and you allow a (n-1)-away ordering, no swaps are needed. Can you find the worst case for d-away for every n and state how many swaps are necessary? (Hint: The result is surprising and quite beautiful.)
5. How many one-away configurations are there for n elements? (Hint: see last hint.)
