# Averaging problem

franktaw at netscape.net franktaw at netscape.net
Tue Nov 27 10:14:41 CET 2007

```Take the n values to be distinct powers of 2^n.  The weight of each
value in the final result is always a power of 2 between 2^0 and
2^-(n-1).
(2^0 occurs only for n=1, but that doesn't affect the argument.)
Looking at the binary expansion of the final average, we can tell
exactly
what weight was assigned to each number.

From the weights, it is easy to determine the exact parenthesization
tree.  The final operation occurs exactly where the running sum of the
weights is 1/2.  If there is more than number on one side of the
operation, the last operation on that side occurs where the sum (on
that side) is 1/4, etc.

------------------------

I don't think that all possible values can be obtained.  For n > 1, any
given number can be given any power of 2 weight between 2^-1
and 2^-(n-1).  This means that operands all the same except for one
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.

-----Original Message-----
From: David Wilson <davidwwilson at comcast.net>

...

The upshot is, for ab = (a+b)/2, I see at most C(n-1) best-case
distinct
values of an n-operand expression, but I don't immediately see exactly
C(n-1) best-case distinct values. I stand ready to be amazed, though.

-------------------------------------------------------------------------
---

Even if we do show that ab = (a+b)/2 leads to C(n-1) best-case distinct
values of n operands, I am bound and determined to get a new sequence,
or
new interpretation of an existing sequence, out of this line of
inquiry.

We agree that for judiciously defined ab, an n-operand expression can
at
most C(n-1) distinct values, one for each parenthesization. However, I
am
skeptical that an n-operand expression can take on any number of
distinct
values between 1 and C(n-1) inclusive. Is there, for example, an
8-operand
expression with exactly 7 values? How many possible numbers of distinct
values can an n-operand expression take on by varying parentheses?

________________________________________________________________________
Check Out the new free AIM(R) Mail -- Unlimited storage and
industry-leading spam and email virus protection.

```