Hello everyone, have a nice day!
At school, I have a problem that is: Given a sequence A consisting of N elements and the task is to remove some elements so that the average of all the remaining elements is the largest. I know the result is the largest value in that sequence, but I don't know how to prove it's the right result.
Please, can someone prove that help me understand?
Thank you to everyone who took the time to read this status!
If there are any grammatical mistakes, please forgive me.
Suppose that there is answer that is larger than maximum element, then there is subsequence $$$\frac{a_1 + a_2 + .. + a_k}{k} > max$$$, so $$$a_1 + a_2 + .. + a_k > max * k$$$, and it's clearly impossible because upper bound of sum $$$a_1 + a_2 + .. + a_k$$$ is that each element is maximum and it's exactly $$$max * k$$$, so $$$a_1 + a_2 + .. + a_k <= max * k$$$, contradaction.
The second proof is that if the added value is greater than $$$avg$$$ then $$$avg$$$, increases, otherwise it decreases. So if the average will be a maximum element, then the addition of new element will be $$$<= avg$$$, because all elements are less than or equal to $$$max$$$.