How to show that maximal subset is same as sum over maximal subset

Question

Consider a collection of positive values, $x_i$, $i=1,\ldots,n$. Is it true that the maximum $k<n$ elements, denoted $\mathcal{K}$, is the same set as the set of elements that results in the biggest sum $\sum_{i\in\mathcal{K'}}x_i$ across all subsets $\mathcal{K}'$ of size $k$? This seems intuitive but I cannot show.

Answer 1

Yes, this is true. Let $\mathcal{K}$ be the set of the largest $k$ elements in our larger set, say $\mathcal{M}$. Now suppose that $\mathcal{K}'$, $|\mathcal{K}'|=k$, is the set such that $$\max_{\substack{\mathcal{S}\subset\mathcal{M} \\ |\mathcal{S}|=k}}\sum_{x\in\mathcal{S}}x=\sum_{x\in\mathcal{K}'}x\qquad\qquad (1)$$ Suppose then that there were some $y_1\in\mathcal{M}\setminus \mathcal{K}'$ such that $y_1>y_2$ for some $y_2\in\mathcal{K}'$. Then we'd have that $|\mathcal{K}'\setminus\{y_2\}\cup\{y_1\}|=k$, yet $$\sum_{x\in\mathcal{K}'\setminus\{y_2\}\cup\{y_1\}}x>\sum_{x\in\mathcal{K}'}x$$ which violates $(1)$. Thus we have that every element in $\mathcal{K}'$ is greater than every element in $\mathcal{M}\setminus\mathcal{K}'$. Since these two sets partition $\mathcal{M}$ and $|\mathcal{K}'|=k$ we know that $\mathcal{K}'$ is exactly the largest $k$ elements in $\mathcal{M}$ and $\mathcal{K}=\mathcal{K}'$.

Note that we don't even need the elements to be positive. Formalizing what you're asking can presumably be done in many ways. In most cases the idea that the largest sum of $k$ elements from a set results from summing the $k$ largest elements in that set would be accepted without proof.