Averaging sequences

[Brendan McKay]

The following problems came up very indirectly in an application.
The application only needs bounds, which are not too hard, but
maybe the exact solution is of interest sequentially.

We are given a multiset of real numbers in [-1..1] with sum 0. We
can apply an "averaging operation" which involves replacing two of
the numbers by their mean. This operation preserves the properties
that the numbers all lie in [-1..1] and sum to 0, but makes them
somehow closer together. Eventually, if we use the averaging
operations wisely, all the numbers will lie in [-1/2..1/2]. The
question is: in the worse case, how many averaging operations does
that take?

Example:             { 0.8,  -0.6,  1.0,  0.1,  -0.5, -0.8 }
Average 2nd and 3rd: { 0.8,   0.2,  0.2,  0.1,  -0.5, -0.8 }
Average 1st and 5th: { 0.0,   0.2,  0.2,  0.1,  -0.5,  0.0 }
Now all the numbers are in [-1/2..1/2], and that took 2 operations.

This multiset needs 3 averaging operations:
{ -0.6, -0.6, -0.6, 0.9, 0.9 }
Apparently no multiset of order 5 needs more than 3 operations,
so a(5) = 3.

I conjecture that a(n) is some rounded version of 2*n/3, and this
is exemplified by a multiset which is about one third equal to +1
and the remainder a tiny bit less than -1/2.  It might be that an
optimal strategy is to always average the largest and smallest
numbers in the multiset.

Replace 1/2 by 1/3 for (I think) a harder problem.

Now to a more complicated problem that also comes from the application.
Suppose there are two sequences instead of one multiset. Each of
the seqeunces is in [-1..1] and sums to 0, and we want to apply
averaging operations to make both sequences in [-1/2..1/2]. The
catch is that we have to average the same two elements of each
sequence. That is, if we average the j-th and k-th elements of the
first sequence, we also have to average the j-th and k-th elements of
the second sequence.

Example:              [ -1.0, -0.3, 0.4, 0.9 ]
                      [ 1.0, 0.0, -0.4, -0.6 ]
Average 1st and 2nd:  [ -0.65, -0.65, 0.4, 0.9]
                      [ 0.5, 0.5, -0.4, -0.6 ]
Average 1st and 4th:  [ 0.125, -0.65, 0.4, 0.125]
                      [ -0.05, 0.5, -0.4, -0.05]
Average 1st and 2nd:  [ -0.2625, -0.2625, 0.4, 0.125 ]
                      [ 0.225, 0.225, -0.4, -0.05]
So that took 3 averaging operations.  Can it be done with 2?
What is the worse case requirement for two sequences of length n?

Then one can have three sequences, etc.  

Brendan.