Averaging problem
Max Alekseyev
maxale at gmail.com
Wed Nov 28 04:20:32 CET 2007
On Nov 26, 2007 1:07 AM, David Wilson <davidwwilson at comcast.net> wrote:
> 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.
There is a somewhat known related problem that for n units and a
replacement operation that replaces *any* (not necessary adjacent) two
numbers with their *halved* average (i.e., x,y are replaced with
(x+y)/4) asks to prove that the resulting single number is at least
1/n.
Back in 2006 in Russian forum
http://lib.mexmat.ru/forum/viewtopic.php?t=3815 we discussed a harder
problem of finding the minimum possible resulting number, and worm2
proved that this minimum number equals
(3*2^k - n) / 2^(2*k+1) where k = [log(n)/log(2)].
I was planning to submit some sequences related to this problem to
OEIS but seem to forget (at least I cannot find anything related now).
Regards,
Max
More information about the SeqFan
mailing list