Averaging problem

[David Wilson]

Suppose we start with a sequence S of n >= 1 real values. At each turn, we 
select two adjacent values at random and replace them with their average. 
After n-1 turns, S is reduced to a single number. This number will depend 
the values in S and on which pairs that chosen to average.

For a given S with n elements, there are (n-1)! ways to apply the averages, 
hence we might expect (n-1)! possible final values for a fortuitously chosen 
S.  It is easy to verify that a sequence S of 1 elements results in 0! = 1 
possible value (the value of its element) after 0 averages. Similarly, a 
sequence S of 2 elements results in 1! = 1 possible value (the average of 
its elements) after 1 average. For n = 3, the sequence S = (1, 5, 9) gives 
the 2! = 2 possible final values 4 or 6 depending on which adjacent pair we 
choose to average first.

At n = 4, however, there are fewer than 3! = 6 possible values. Starting 
with a sequence of 4 elements, if we average the first pair, then the last 
pair, then the only pair, we end up with the same value as when we average 
the last pair, then the first pair, then the only pair. This means there are 
at most 5 distinct final values (in fact, there are sequences of 4 elements 
with 5 final values, e.g, (8, 16, 32, 64), which has final values 20, 26, 
30, 40, and 43.

The question is, for a sequence of n elements, what is the largest possible 
number final values? The sequence begins 1, 1, 2, 5, ... for n = 1, 2, 3, 4, 
...