# max and min of a sum

## Recommended Posts

I would appreciate very much your help or direction to solve the problem.

Looks like equation

Q=SUM(ABS(B-Ai))

has got min and max values

with the assumptions

0<B<1

0<=Ai<=1

SUM(A1:AK)=1

and i is a natural number from 1 to K

Looks like the Qmax and Qmin depend on B and K only. I failed to find general solution for Qmax and Qmin.

I attach the pdf with the problem written in Word Equation instead of Excel manner

Q.pdf

Edited by Pawel Wembley

##### Share on other sites

Hello Pawel.

The mimimum $Q_{min}=\max(KB-1,0)$ is calculated as follows:

$\sum_{i=1}^{K}|B-A{_i}|\geq 0$ is trivial, and reached if all $A{_i}$ are equal to $B$.

If $KB-1>0$ then the minimum is not reached at 0, but at $\sum_{i=1}^{K}|B-A{_i}|\stackrel{|x|\geq x}{\geq}\sum_{i=1}^{K}(B-A{_i})\$ $=KB-\sum_{i=1}^{K}A{_i}\ \stackrel{\sum_{i=1}^{K}A{_i}=1}{=}KB-1$. This minimum value is reached if and only if $A{_i}<B \forall i$.

In the case $KB-1<0$, you have $B<\frac{1}{K}$, so at least one of the $A{_i}$ is larger than $B$ (by the Pigeon Principle). Which means that $KB-1$ can't be reached. In that case, the mimimum is 0.

For the maximum $Q_{max}=1+B(K-2)$:

$\sum_{i=1}^{K}|B-A{_i}| \stackrel{extend}{=}\sum_{i=1}^{K}(B+A{_i})-\sum_{i=1}^{K}(B+A_{i}-|B-A{_i}|)$ $=KB+1-\sum_{i=1,A{_i}>B}^{K}(B+A{_i}+B-A{_i})-\sum_{i=1,A{_i}\leq B}^{K}(B+A{_i}-B+A{_i})$ $=KB+1-\sum_{i=1,A{_i}>B}^{K}(2B)-\sum_{i=1,A{_i}\leq B}^{K}(2A{_i})$. This will get maximal if you have $A{_i}=0 \forall A{_i}\leq B$, when it will be equal to $KB+1-2B \cdot 1_{A{_i}>B}$.

If one of the $A{_i}$ is equal to $1$ (and all other $A_{i}$ are $0$), this will take its maximum value $KB+1-2B \cdot 1=1+B(K-2)$.

Edited by renerpho

##### Share on other sites

Hi Quark, it is great. Big thanks and regards.

## Create an account

Register a new account