2
$\begingroup$

This question already has an answer here:

I didn't finish it, though I'd like to know if I'm on the right track. Let's suppose our reals are indexed in decreasing order: $a_1 \geq a_2 \geq \dots \geq a_{99} \geq a_{100}$. Clearly $a_1 \geq 0 \geq a_{100}$. Hence, we know the sets $A_1 = \{a_1, a_2, \dots, a_k\}$, $A_2 = \{a_{k+1}, a_{k+2}, \dots, a_{100}\}$ are nonempty sets of nonnegative and nonpositive reals respectively.

So we can say with confidence that there's at least ${k}\choose{2}$ nonnegative pairwise sums. If $k\geq 15$, our job is done.

Let's suppose $k<15$. This implies $|A_1|<15, |A_2|>85$. We also have the following equivalence:

$$a_1 + \dots + a_k + a_{k+1} + \dots + a_{100} = 0 \ \ \iff \\ a_1 + \dots + a_k = -\big( a_{k+1} + \dots + a_{100} \big) \ \ \iff \\ a_1 + \dots + a_k = |a_{k+1} + \dots + a_{100}|$$

It's easy to see that for every ${100-k}\choose{k}$ subset of $k$ elements of $A_2$ (let's call it $A_{2_k}$), some element in $A_1$ is greater than $\inf |A_{2_k}|$. So we would then have that there's at least

$${k\choose 2} + {100-k\choose{k}} $$

nonnegative pairwise sums. (Is this binomial coefficient necessarily greater than $99$? I feel like it may be, but I don't know how to prove it).

$\endgroup$

marked as duplicate by Martin R, John Omielan, metamorphy, Cesareo, awkward Jul 19 at 13:00

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

Your calculation is on the right track. It suffices to show that, when $k\in [1,15)$ we have that $$ \binom{100-k}{k}\geq 99.\tag{1} $$ Note that equality holds when $k=1$. Moreover, $$ \binom{100-(k+1)}{k+1}=\frac{(100-2k)\cdot (99-2k)}{(k+1)(100-k)}\binom{100-k}{k}. $$ Since $(100-2k)\cdot (99-2k)\geq (k+1)(100-k)$ for $k\in [1,15)$, it follows that the sequence of binomial coefficients in question is increasing in the given range of $k$. This proves $(1)$.

If you need an extra hint to prove $(100-2k)\cdot (99-2k)\geq (k+1)(100-k)$ for $k\in [1,15)$, note that the crude bound $500\cdot 15 < 9800$ is enough (after multiplying everything out).

However, you have neglected an important detail in your proof. Namely, given a $k$-element subset of $A_2$ you have shown that some element of the $k$-subset can be paired with some element of $A_1$. But you have not shown that this can always be done in a distinct way, for distinct pairs of $k$-subsets. Thus, even though there are enough $k$-subsets (which my calculation in this answer shows) we have no guarantee that we get that same number of pairs (by your argument). It is possible this could be patched with some work... but it is not obvious to me at least.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.