Jtdylktuy

We are given $2k+1$ positive numbers whose sum is $1$. Can we always find two disjoint subsets of $k$ numbers such that the sum of each subset is at most $1/2$?

When $k=1$, this is easy: we have $3$ positive numbers whose sum is $1$, so at most one number is more than $1/2$, so at least two numbers are at most $1/2$.
Is it true for $k>1$?

Note: assuming the sets exist, it is clear that their union is all of the points with one exception. We might as well assume that the missing point is the largest (if not, then the largest is in one of the two sets and we can swap it out for the missing element without hurting the desired sum).

Work inductively. Suppose we are done for the case $k-1$. Consider the case corresponding to $k$. Order our $2k+1$ numbers as $a_1≤a_2≤cdots ≤a_{2k+1}$ . Now consider the $2k-1$ points ${a_1,cdots, a_{2k-1}}$. Of course these sum to $1-a_{2k+1}-a_{2k}$. Define ${b_i}_{i=1}^{2k-1}$ by $b_i=frac {a_i}{1-a_{2k+1}-a_{2k}}$ Now the $b_i$ form a set of $2k-1$ numbers that sum to $1$ so we can apply the inductive hypothesis to this set. We get a partition of $b_1,cdots, b_{2k-2}$ into two sets each of which sums to less than $frac 12$. Multiplying by $1-a_{2k+1}-a_{2k}$ we get a partition of $a_1,cdots, a_{2k-2}$ into two sets each of which sums to less than $frac {1-a_{2k+1}-a_{2k}}2$. Call these two sets $S_1,S_2$. We now claim that we can adjoin $a_{2k-1}$ to one of them and $a_{2k}$ to the other to get the desired partition of size $k$.

To see this, suppose we add $a_{2k}$ to $S_1$. Then the new sum is less than $$frac {1-a_{2k}-a_{2k+1}}2+a_{2k}=frac {1+a_{2k}-a_{2k+1}}2$$ But by the ordering, $a_{2k}≤a_{2k+1}$ so the numerator here is at most $1$ and we are done. Of course $a_{2k-1}$ is not greater than $a_{2k}$ so the same argument works for $S_2$.

Based on the two previous answers, here is a simpler algorithm.

Order the $2k+1$ numbers in increasing order, $a_1leqcdots leq a_{2k+1}$.

Consider first the $k$ numbers with even indices: each number in this set is weakly smaller than the number immediately after it, which is not in this set. Hence, the sum of these numbers must be at most $1/2$.

Consider next the $k$ numbers with odd indices, except the last one: again each number in this set is weakly smaller than the number immediately after it, which is not in this set. Hence, the sum of these numbers must be at most $1/2$ too.

Yes, here's an explicit algorithm for constructing two disjoint $k$-subsets.

Let $H$ be a family/multiset of positive numbers indexed by $mathbb{N}_{le(2k+1)}$, with $mathbb{N}$ excluding zero.

Let's further constrain $H$ to be weakly monotonically increasing in the index, so $H_{2k+1}$ is the co-largest element.

Suppose $H_{2k+1} ge frac{1}{2}$ , then $H_{(1cdots k)}$ and $H_{(k+1 cdots 2k)}$ both have sum $le frac{1}{2}$ and we're done.

Suppose $H_{2k+1} le frac{1}{2}$ , then let's define the champion $k$-subfamily $c$ and its set of indices $gamma$ by the following algorithm.

1. The very first thing we do is exclude the largest index $2k+1$ (which corresponds to the greatest element of $H$), none of the candidate subsets involve this index.


2. Enumerate all the $k$-subsets of $mathbb{N}_{le(2k)}$ , call the subset under consideration $w$
   


3. reject all $w$'s for which $sum_{j in w}H_j$ is greater than or equal to $frac{1}{2}$ .


4. reject all $w$'s that do not have the maximum possible sum of any of the remaining $w$'s.


5. Of the remaining sets, pick the greatest remaining set by comparing the greatest indices one at a time of $w$ . For instance ${5,4,1}$ beats ${5,3,1}$ because $4 > 3$ . This tiebreaker is completely arbitrary, it's just there to guarantee uniqueness.


6. 
   $c$ is $w$ and $gamma$ is $H_c$ .

Note that at least one subset $w = {1, cdots, k}$ makes it past step 3, so the algorithm always produces a unique champion subset of indices $c$, which corresponds to a multiset $gamma = H_c$.

Let's define multiset indexed by the champion complement set $H[(mathbb{N}le 2*k) setminus c)]$. Henceforth $d = (mathbb{N}le 2*k) setminus c$, and $delta = H_d$ .

$gamma$ has sum less than $frac{1}{2}$ by construction. We will show that $delta$ also has sum less than $frac{1}{2}$ .

If $sum delta = sum_{j in d}H_j lt frac{1}{2}$, then we have found a pair of disjoint subsets $c$ and $d$ each with sum less than $frac{1}{2}$, as required.

If $sum delta = frac{1}{2}$, then then the sum of $sum gamma$ and $H_{2k+1}$ is $frac{1}{2}$ .

We will define an operation in terms of $gamma$ and $delta$ to produce a new multiset $gamma'$ with a larger sum than $gamma$, but still less than $frac{1}{2}$ .

Pick the largest element of $delta$, tie-breaking on the index if necessary. Call its index $t in d$ . Pick the largest element of $gamma$ less than $t$ , call its index $s in c$ .

If there is no $s in c$, then $sum delta le sum gamma$. $sum gamma < frac{1}{2}$ by construction, so there's a contradiction. Therefore there is an $s in c$ less than $t in d$ .

$t-s$ is positive by construction. $t-s$ is also less than $H_{2k+1}$ because it is a difference of two positive numbers, each of which is smaller than $H_{2k+1}$ .

Define $gamma'$ as the multiset obtained by removing the element with index $s$ from $gamma$ and adding the element with index $t$ from $delta$ . $gamma'$ is a better candidate for champion than $gamma$ . Therefore $gamma$ is not champion.

If $sum delta gt frac{1}{2}$, then we can repeat the construction defined above for producing $gamma'$ . $gamma'$ has sum less than $frac{1}{2}$ and is a better candidate for champion set than $gamma$ . Therefore $gamma$ is not champion.