Partitioning a finite set of real numbers into two disjoint classes whose sum is less than 1/2

34 Views Asked by At

I want to prove the following result: If $a_1, ..., a_{n+1} \in \mathbb{R}_{\geq 0}$ ($n \geq 2$) are non-negative real numbers such that $a_{n+1} \geq a_i$ for each $i = 1, ..., n$ and we have $a_1 + a_2 + a_3 + \cdot \cdot \cdot + a_{n+1} = 1$, then the set $\{a_1, ..., a_n\}$ can be partitioned into two disjoint classes such that the sum of each class does not exceed $\frac{1}{2}$. I came up with a proof of my own but it's different from the one on the book so i want to know if i did something wrong... So let's start: First suppose that $n+1$ is even, so we have $n+1 = 2k$ for some positive integer $k$ (note that $k \geq 2$). Now i can wlog reorder my $a_i$ ($i = 1, ..., n$) in a way such that i have $a_1 \leq a_2 \leq \cdot \cdot \cdot \leq a_{2k}$. Now notice that $a_1 + a_3 + \cdot \cdot \cdot + a_{2k-1} \leq a_2 + a_4 + \cdot \cdot \cdot + a_{2k}$ and so, adding the quantity $a_1 + a_3 + \cdot \cdot \cdot + a_{2k-1}$ on both sides and using the hypotesis $\sum_{i=1}^{n+1} a_i = 1$ i obtain $a_1 + a_3 + \cdot \cdot \cdot + a_{2k-1} \leq 0.5$. Now just note that $a_2 + a_4 + \cdot \cdot \cdot + a_{2k-2} \leq a_3 + a_5 + \cdot \cdot \cdot + a_{2k-1} \leq 0.5$. So the partition $\{ a_1, a_3, ..., a_{2k-1}\}$, $\{a_2, a_4, ..., a_{2k-2}\}$ is what we were looking for. If n + 1 is odd then the proof is identical. (i can write it if you really need it)