minimalna stoinost

[N.Stavrev]

Намерете минималната стойност на израза [tex]A=\sum_{i=1}^{2l }{|x-i| }+\sum_{i=1}^{2l+1 }{|x-i|}+...+\sum_{i=1}^{2l+2r+1 }{|x-i|}[/tex] , [tex]r,l\in N[/tex]

[Станислав]

Заместваш с [tex]x=2l[/tex].

[N.Stavrev]

Защо ?

[drago]

Заместваш с [tex]x=2l[/tex].

То не само въпроса е защо, но това не е вярно, ако си имал предвид, че минимума се достига за това x.

[Станислав]

[tex]\sum_{i=1}^n |x-i|[/tex] достига минимума си за всяко [tex]x\in[1,n][/tex]?

[drago]

[tex]\sum_{i=1}^n |x-i|[/tex] достига минимума си за всяко [tex]x\in[1,n][/tex]?

???
Достига минимума си в зависимост от четността на n. Или в средната точка(точките са 1,2,...,n) или в средния интервал!

[drago]

След леки преобразувания:
[tex]A=\sum_{j=1}^{2l}(2r+2)|x-x_j| + \sum_{j=1}^{2r+1}(2r+2-j)|x-(2l+j)|[/tex]
Сега малко по-общо, нека са дадени: [tex]x_1 \lt x_2 \lt ... \lt x_n.[/tex] и тегла [tex]a_1,...,a_n \gt 0.[/tex]
Търсим min на [tex]S(x)=\sum_{j=1}^{n}a_j|x-x_j|[/tex].
Нека [tex]x \in (x_k,x_{k+1})[/tex].
Даваме на x нарастване [tex]\Delta x \Rightarrow \Delta S= \Delta x(\sum_{j=1}^{k}a_j-\sum_{j=k+1}^{n}a_j).[/tex]
От тук се вижда че ако има [tex]k[/tex] т.ч. [tex]\sum_{j=1}^{k}a_j=\sum_{j=k+1}^{n}a_j[/tex], то min се достига за [tex]\forall x \in [x_k,x_{k+1}][/tex].
иначе min се достика в [tex]x_k[/tex], където [tex]k[/tex] има свойството:
[tex]\sum_{j=1}^{k-1}a_j \lt \sum_{j=k}^{n}a_j[/tex]
[tex]\sum_{j=1}^{k}a_j \gt \sum_{j=k+1}^{n}a_j[/tex]
Сега трябва да съобразим нещата за конкретния случай:
[tex]a_j=(2r+2); j=1,...,2l.[/tex]
[tex]a_j=2r+2-(j-2l); j=2l+1,...,2l+2r+1.[/tex]
[tex]x_j=j; j=1,...,2l+2r+1.[/tex]

[N.Stavrev]

За да намерим минимума на дадения израз, ще намерим [tex]P_{min}(x)=\sum_{i=1}^{n=2l }{|x-i|}[/tex].
Нека [tex]n[/tex]е максимално и [tex]k=1,2,...[/tex], намираме
[tex]P(k+1)=|k+1-1|+|k+1-2|+...+|k+1-n|[/tex] и [tex]P(n-k)=|n-k-1|+|n-k-2|+...+|n-k-n|[/tex]
оттук виждаме, че [tex]P(k+1)=P(n-k)[/tex].Нека [tex]x=\frac{n}{ 2}[/tex], намираме [tex]P(\frac{n}{2 })=|\frac{n}{2 }-1|+|\frac{n}{ 2}-2|+...+\frac{n}{ 2}[/tex].Нека [tex]p>0[/tex],тогава [tex]P(\frac{n}{2 }+p)>P(\frac{n}{2 })[/tex], но от[tex]P(k+1)=P(n-k)[/tex] следва, че изразът е растящ и за всички [tex]x[/tex] преди [tex]\frac{n}{2 }[/tex].
Нека [tex]x=\frac{n}{2 }+m , m\in(0;1)[/tex],намираме[tex]P(\frac{n}{2 }+m)=|\frac{n}{2 }+m-1|+|\frac{n}{2 }+m-2|+...+|\frac{n}{2 }+m-\frac{n}{2 }|+|\frac{n}{2 }+m-\frac{n}{ 2}-1|+...+|\frac{n}{ 2}+m-n|[/tex] където [tex]n[/tex] е максимално, тогава модулите до [tex]\frac{n}{ 2}[/tex]-то падат, а при останалите се обръща знака,тогава точно на [tex]\frac{n}{2 }[/tex] на брой събираеми знака пред [tex]m[/tex]ще стане минус, а на другите [tex]\frac{n}{ 2}[/tex] ще остане плюс, но щом [tex]n[/tex] е максимално следва, че израза става константа т.е при [tex]x\in[k+1;n-k][/tex]израза достига своя минимум, като [tex]n[/tex]е четно.Ако [tex]n[/tex]е нечетно следва и израза да не е симетричен или е невъзможно минималната стойност да се достига при безброй много [tex]x[/tex]т.е при една стойност.Нека [tex]n'=n-1[/tex] тогава израза [tex]P(n')[/tex] се получава като се премахне [tex]|x-n|[/tex] а минималната стойност на [tex]P(n')[/tex] ще получим като премахнем максималната на [tex]|x-n|[/tex]от минималната на[tex]P(n)[/tex] но понеже израза[tex]P(n)[/tex]е симетричен следва да отбележим, че колкото последното му събираемо е по-малко, то другите му са по-големи и обратно ако е по-голямо, то другите са по-малки, а щом говорим за интервала [tex][\frac{n}{2 };\frac{n}{2 }+1][/tex]и за максимална стойност на последното събираемо, то можем да кажем, че категорично минималната стойност на израза ще достигнем при [tex]\frac{n}{ 2}=\frac{n'+1}{2 }[/tex].От [tex]n=2l[/tex] следва, че минималната стойност ще получим при [tex]x=l[/tex] [tex]P(l)=|l-1|+|l-2|+...+|l-l-1|+|l-l|+|l-l-1|+...+|l-2l|[/tex] или [tex]\sum_{i=1}^{l-1 }{i}+\sum_{i=1}^{l }{i}=\frac{l(l-1)}{2 }+\frac{l(l+1)}{2 }=l^2[/tex].Нека [tex]n[/tex] е нечетно, тогава ще заместим с [tex]x=\frac{n+1}{2 }=l+1[/tex] т.е [tex]P(l+1)=|l|+|l-1|+...+1+0+|l+1-l-2|+|l+1-l-3|+...+|l+1-2l-1|=2\sum_{i=1}^{l }{i}=\frac{2l(l+1)}{2 }=l(l+1)[/tex]. Окончателно [tex]\sum_{i=1}^{2l }{|x-i|}+\sum_{i=1}^{2l+2 }{|x-i|}+...+\sum_{i=1}^{2l+2r }{|x-i|}\ge \sum_{i=0}^{r }{(l+i)^2}[/tex] и [tex]\sum_{i=1}^{2l+1 }{|x-i|}+\sum_{i=1}^{2l+3 }{|x-i|}+...+\sum_{i=1}^{2l+2r+1 }{|x-i|}\ge \sum_{i=0}^{r }{(l+i)(l+i+1)}[/tex] събираме ги и получаваме [tex]\sum_{i=1}^{2l }{|x-i|}+\sum_{i=1}^{2l+1 }{|x-i|}+...+\sum_{i=1}^{2l+2r+1 }{|x-i|}\ge \sum_{i=0}^{r }{(l+i)(2(l+i)+1)}[/tex]

[drago]

Нали задачата беше да се намери мин. стойност ?! Това, което е направено е оценка от долу, при това груба. Всяко събираемо се оценява с мин. си стойност. Тя не се достига.