First of all, suppose we have a solution for N vases, then by removing vases M+1 through N, we will have a solution for M vases for any M less than N. Thus, we only need to find solutions in a few particular cases of N, as long as those cases get arbitrarily large it will be good enough (for example, we are going to wind up having a solution that works for N being a power of 2, since any number can be expressed a less than some power of two, you can simply grab that larger solution and remove the extra vases).
For future considerations, it will be slightly easier to subtract 1 from the heights of all the vases, so they are numbered 0 through N-1, rather than 1 through N.
We must arrange things so that no number is between two numbers it is the average of, so x cannot appear between x+a and x-a for any a. Note that the average of two even numbers is even and the average of two odd numbers is odd, and the average of an even number and an odd number is not an integer. This suggests that we place all the even numbers on one side, and all the odd numbers on the other. That way there is no concern of the "left side" and the "right side" having anything dangerous in between them, we can simply treat them independently.
Within the even ones, we can simply half them and solve the N/2 case. With the odd ones, we can subtract 1 from them and then half them and use the N/2 solution. Thus we can see that if we can solve N/2, we can solve N. This is why we will get solutions for powers of two, we simply must start by solving the case N=2 (this is trivial, the solution is (0 1)).
So, if we wanted to solve N=4, we have 0 1 2 3 to place in order, begin with the evens on the left and odds on the right and we get (0 2 1 3) as our solution. For N=8 we being by sorting them to (0 2 4 6 1 3 5 7) next treat 0 2 4 6 as 0 1 2 3 to get (0 4 2 6) and treat 1 3 5 7 as 0 1 2 3 to get (1 5 3 7), so the solution is (0 4 2 6 1 5 3 7).
There is another way to generate this solution, begin by writing out the numbers 0 through N-1 in binary
000Next, reverse the digits
001
010
011
100
101
110
111
000Next, read them off as they are to get (0 4 2 6 1 5 3 7), which is the same solution.
100
010
110
001
101
011
111
That first algorithm to get the solution is clean enough, and I was pretty happy to consider it the solution, but the second solution involving binary numbers in reverse is really cool (and I did not come up with it, I saw it on xkcd). Its a bit harder to prove that it always works though, but its not so counterintuitive that its impossible to believe. Naturally, if you want the solution for N that is not a power of two, just solve a larger N that is a power of two and ignore the extra numbers, so for N=5 we have (0 4 2 1 3), which after adding 1 becomes (1 5 3 2 4) which works as a solution.
