N dwarfs of heights 1,2,3...,N are arranged in a circle. For each pair of neighbouring dwarfs the positive difference between their heights is calculated; the sum of these N differences is called the "total variation" V of the arrangement. Find (with proof) the maximum and minimum possible values of V.

Peter

Part of this is easy. Suppose the numbers 1,2,...,n-1 are arranged on a circle (in that order). Consider the effect on the total variation of inserting n between a,b (where b> a and a,b are consecutive in the circle of 1,2,...,n-1).

The change in total variation is:

(n - a) + (n - b) - (b - a) = 2n - 2b = 2(n - b) > = 2

This means that the total variation must go up by at least two each time n increases by 1. When n = 2 the total variation is 2, so in general the total variation > = 2n - 2. Clearly this inequality is an equality in the case where the numbers appear in the order:

1,2,...,n

Therefore the minimal total variation is trivially 2n - 2. Finding the maximal will be rather more tricky I suspect.

OK, I think you can answer the maximal part by considering the circle with the numbers p,p+1,...,q then finding where the numbers p-1,q+1 should be placed to cause the maximal increase in the total variation. I'll investigate more thoroughly in the morning.

That the minimal total variation is 2n - 2 is obvious if you think about it for a moment: if you go once round the circle, starting at 1, then as you go round you have to get all the way up to n at some point and then all the way back down to 1.

The minimum is achieved whenever you go 'directly' up to n and 'directly' back down again, so when the numbers are arranged

1, a₁ , a₂ , ..., a_r , n, b₁ , b₂ , ..., b_s ,

where a₁ < a₂ < ... < a_r and b₁ > b₂ > ... b_s .

For the maximal part, following on along the suggested line of thinking, I get that the maximum is

(1/2)(n - 1)(n + 1) if n is odd

or

(1/2)(n² ) if n is even

though I haven't got time to post the solution now - I will do tomorrow if no-one beats me to it (or points out that this isn't correct!).

James.

I agree with James' answers. The solution to the first part is nice and intuitive; for some reason I didn't think of it that way! Still it's easy to arrive at 2n - 2 even if you don't think of that.

For the second part, I have a slightly different way of doing it than the way I suggested at 11:34 yesterday. Suppose the numbers are arranged (going round the circle) in the order b₁ , b₂ , ..., b_n . Then the total difference will be:

e₁ (b₂ - b₁ ) + e₂ (b₃ - b₂ ) + ... + e_n-1 (b_n - b_n-1 ) + e_n (b₁ - b_n )

where e₁ ,...,e_n are each +1 or -1.

This can then be re-arranged as:

b₁ (-e₁ + e_n )
+ b₂ (-e₂ + e₁ )
+ b₃ (-e₃ + e₂ )
+ ...
+ b_n (-e_n + e_n-1 )

Letting q₁ = -e₁ + e_n , q₂ = -e₂ + e₁ , q₃ = -e₃ + e₂ , ..., q_n = -e_n + e_n-1 we see that the total variation is:

q₁ b₁ + q₂ b₂ + ... + q_n b_n

where each q_i is one of -2,0,2. Furthermore q₁ + ... + q_n = 0, so the number of q_i s which are -2 is the same as the number which are +2.

Then supposing we want to maximise:

y = q₁ b₁ + q₂ b₂ + ... + q_n b_n

only on the constraint that each q_i is one of -2,0,2 and the number of -2s is the same as the number of +2s. Without loss of generality we can set b_i = i and then in that case we see immediately that the sequence q_i is increasing (otherwise, if q_j < q_i with i < j, swap around q_i , q_j and we get a larger value of y).

Moreover, no more than 1 of the q_i s can be zero. If q_i = q_j = 0 (with i < j), then we would be able to increase y by changing q_i to -2 and q_j to +2 (keeping the others fixed).

If n is even then we cannot have exactly one of the q_i s zero, and if n is odd we cannot have none of the q_i s 0. Therefore, to maximise y the sequence q_i must be:

-2,-2,...,-2,0,2,2,...,2 (n odd)
-2,-2,...,-2,2,...,2 (n even)

where of course there are equally many -2s as +2s in either case.

Therefore the maximal total variation cannot possibly be more than:

2((n/2+1) + (n/2+2) + ... + n) - 2(1 + 2 + ... + n/2)
= n(n+1) - n/2(n/2+1) - n/2(n/2+1)
= n² /2

when n is even and

2((n+3)/2 + (n+5)/2 + ... + n) + 0((n+1)/2) - 2(1 + 2 + ... + (n-1)/2) = 2(n(n+1)/2 - (n+1)(n+3)/8 - (n-1)(n+1)/8) = (n-1)(n+1)/2

when n is odd. Can we get equality? Yes, easily in both cases:

n Even: arrange them as 1,n,2,n-1,3,n-2,...,n/2,(n+2)/2

n Odd: arrange them as 1,n,2,n-1,...,(n-1)/2,(n+1)/2

Therefore the maximal total variation is n² /2 (n even) and (n-1)(n+1)/2 with n odd. The minimal total variation is 2n-2.