Averaging problem

[Maximilian Hasler]

> different value will produce n-1 distinct values.  While 1 value is of
> course always obtainable (just take all operands equal), I don't see
> any way to get strictly between 1 and n-1 distinct values.  I don't
> know if there are other unobtainable values between n-1 and C(n-1),
> but I expect there are.

If you choose an element in the middle different from all others, you
get less than n-1 values.
e.g., for  n=7, x=[0,0,0,0,0,0,1], you get 6 possibilities  [1/16,
1/2, 1/32, 1/4, 1/64, 1/8]
but for x=[0,0,0,1,0,0,0] you only get 5 possibilities : [1/16, 1/32,
1/4, 1/64, 1/8]

another example, for [0,1,0,0] (n=4), you only get 2 possibilites: [1/4, 1/8]

I suggest to consider the n x C(n-1) matrix  An  of the coefficients
of x1,...,xn in the C(n-1) different expressions for the averages.
For a given vector (x1,...,xn) we then obtain the possible values by
multiplying this vector
(as 1 x n matrix) by the matrix An.
e.g. for n=4 we have
A4 =
[1/2 1/2 1/4 1/4 1/8]
[1/4 1/8 1/4 1/8 1/8]
[1/8 1/8 1/4 1/8 1/4]
[1/8 1/4 1/4 1/2 1/2]

The 2nd line only contains 2 distinct values and not n-1 = 3.

Regards,
Maximilian

(some more or less dirty PARI code follows, just for the records
(mine, basically))

dw(X, S=[], v, n) =
n=#X;forvec(i=vector(n-1,j,[1,n-j]),v=X;for(j=1,n-1,v[i[j]]=(v[i[j]]+v[i[j]+1])/2;(v=vecextract(v,Str("^",i[j]+1))));S=setunion(S,[v[1]]));eval(S)

dw([x1,x2,x3])
%327 = [1/2*x1 + (1/4*x2 + 1/4*x3), 1/4*x1 + (1/4*x2 + 1/2*x3)]

dw([0,0,0,0,0,0,1])
%318 = [1/16, 1/2, 1/32, 1/4, 1/64, 1/8]

dw([0,0,0,0,0,1,1])
%319 = [1/16, 1/2, 1/32, 1/4, 1/8, 17/32, 17/64, 3/16, 3/32, 3/4,
3/64, 3/8, 33/64, 5/16, 5/32, 5/64, 5/8, 9/16, 9/32, 9/64]
dw([1,0,0,0,0,0,1])
%320 = [1/2, 1/4, 17/32, 3/16, 3/4, 3/8, 33/64, 5/16, 5/8, 9/16, 9/32]

dw([0,0,0,1,0,0,0])
%321 = [1/16, 1/32, 1/4, 1/64, 1/8]

(14:39) gp > eval(dw([0,1,0,0]))
%323 = [1/4, 1/8]
(14:39) gp > eval(dw([0,1,1,0]))
%324 = [1/2, 1/4, 3/8]

mm(n)=X=vector(n,i,eval(Str("x",i)));n=dw(X);matrix(#n,#X,i,j,polcoeff(n[i],1,X[j]))

mm(4)
%326 =
[1/2 1/4 1/8 1/8]
[1/2 1/8 1/8 1/4]
[1/4 1/4 1/4 1/4]
[1/4 1/8 1/8 1/2]
[1/8 1/8 1/4 1/2]