Vases In A Line

Blogging is for chumps, I'm on extended vacation (also known as semi-unemployed). Anyway, time for a puzzle that I found on the forums at xkcd:
There is a museum with N vases they wish to arrange on a display. The vases are such that the first one has a height of 1cm, the second one has height of 2cm, and so on such that the Nth one has a height of N centimeters. The people at the museum wish to arrange the vases in a linear display in a special way, such that if we have three vases with heights a,b,c, with b being the average of a and c, b does not appear between a and c.

The puzzle is to come up with an algorithm that will generate an arrangement of numbers 1 through N such that no number appears between two numbers it is the average of.
So, for example if N=5, we could not have 3 appear anywhere between 2 and 4, or anywhere between 1 and 5, 2 could not appear between 1 and 3, and 4 could not appear between 3 and 5. An acceptable answer there would be (1 5 3 2 4).

Arrangements and Derangements

So, it seems that finishing my thesis has slowed down my blogging. Blogging was done as a way to slack from work, and now I don't really do much work anymore, leaving me with nothing to slack from. Basically, I need to start looking for a job so I can slack off with maximum efficiency.

Alright, time to look at the solution to the sorting puzzle from last time. I guess the solution was given in the comments, which means that I actually have something of a readership I guess (which is a good thing?), anyway, I have no problems with people posting solutions in the comments, but I'm going to do my own solution as usual.

First, lets try to solve it in some simple cases. We already know that the sequence (2 1) takes two moves, how about the sequence (3 1 2). There seems to be no reason to hold any of them in place, and a randomization has an equal chance of going to any of (1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1). The number of steps those are away from the sorted form is 0, 2, 2, k, k, 2, respectively, (knowing that, say, (1 3 2) is two steps away on average) where k is the number of steps (3 1 2) is away. This allows us to say that
k=1/6(0+1)+3/6(2+1)+2/6(k+1)

which can be solved to get k=3. So this solves the N=3 case completely.

For N=4 we have a bit more of a complicated situation, it is clear that anything such as (_ _ _ 4) reduces to the N=3 case, but we have two separate things to solve, one is things of the form (2 3 4 1) where we have everything out of place, and the other is of the form (2 1 4 3) where we have two separate groups. We already know that it is possible to solve (2 1 4 3) in two steps by doing the first two separate from the second two, but it might be better somehow to just ignore that they are two separate cycles and randomize the whole thing. If it is better, then (2 3 4 1) will be less than 4 steps away on average. If it is more than 4 on average, then we should treat cycles separately, and if it is exactly 4 then it does not matter if we isolate cycles.

First, we will treat cycles separately, and let g(n) be the number of moves it takes on average to sort an n-cycle with each element out of place to the right by one (or left if you like). We have seen g(2)=2, g(3)=3 and trivially g(0)=0, g(1) isn't really a thing since you can't have a cycle of 1 with each one being out of place. Anyway, from a 4-cycle we have 24 places we can go, 1 of them is (1 2 3 4), the solution, 4C2 of them are 2-cycles (like (2 1 3 4)), 4C2/2 of then are two 2-cycles (like (2 1 4 3)), 8 of them are 3-cycles (you can see this by locking one of them down and there are two ways the remaining three are out of place), and the remaining 6 of them are 4-cycles. We can then see that
g(4)=1/24(0+1)+6/24(g(2)+1)+3/24(g(2)+g(2)+1)+8/24(g(3)+1)+6/24(g(4)+1)

which we can solve to get g(4)=4. If we chose the other strategy of just treating two 2-cycles as a 4-cycle, we would replace the term g(2)+g(2) with g(4) instead, and still get the solution g(4)=4, showing that the strategies are the same.

Given that, we might as well only lock down ones that are in the correct place, and not worry about the smaller cycles. Let f(n) be the number of steps it takes to get from a completely unsorted list of n elements to a sorted one ("completely unsorted" means none are in the correct place). Mathematicans have a name for a completely unsorted list, they call it a derangement, and the standard notation for the number of derangements of n elements is !n. A few early ones are !0=1, !1=0, !2=1, !3=2, !4=9. Our earlier strategy for finding f(4) can be expressed as
f(4)=!0/4!(f(0)+1)+!1/4!(f(1)+1)+!2/4!(f(2)+1)+!3/4!(f(3)+1)+!4/4!(f(4)+1)

that is, f(4) is the chance you get k elements in the wrong place, times f(k)+1, summed over k. The chance that exactly k elements are in the wrong place is !k/4!. f(1) isn't really defined, but !1 is zero anyway, I just included that term for completeness.

From this we can deduce the general form
f(N)=Σ !k/N!(f(k)+1)

summed k from 0 to N. If we hypothesize that f(k)=k for all k less than N, we can then proceed to prove f(N)=N, though it is rather tedious to do it this way.

The more intuitive way to get f(N)=N was given in the comments, throwing N elements into the air, each one has a 1/N chance of landing in the right spot, and you threw N of them, so on average one of them will land in the right spot. Thus it takes N steps.