Let $a_1, a_2, a_3, ... , a_n$ and $\alpha$ be n+1 non-zero real numbers. Prove that there are at most $n\choose \left\lfloor\frac{n}{2}\right\rfloor$ subsets $A\subset[n]$ such that $\displaystyle\sum\limits_{i\in{A}} a_i=\alpha$

I'm not quite sure how to approach this but I suspect it is something to do with the fact that every antichain is size at most $n\choose \left \lfloor \frac{n}{2} \right \rfloor$. I was thinking that all such $A$ that satisfy the condition could somehow relate to an antichain, but I don't quite see how this works, especially since if (say) $x_1+x_2=\alpha$ and $x_1+x_2+x_3+x_4=\alpha$ this would relate to the sets $\left\{ {1, 2}\right\}$ and $\left\{ {1, 2, 3, 4}\right\}$ which clearly isn't part of an antichain.

Any help would be very much appreciated!

  • $\begingroup$ Please do not delete questions with good answers. Others have devoted effort to answer your question; deleting the question is disrespectful of their effort and prevents others from benefiting from your question and its answers. $\endgroup$ – robjohn Aug 21 '13 at 17:45

The general case reduces to the case of positive weights, which is immediately solved by Sperner's theorem. Define:

$P$ to be the multiset of positive $\alpha_i$'s,

$Q$ to be the multiset of negative $\alpha_i$'s (the complement of $P$)

$Q'$ to be $Q$ with signs of all elements reversed to positive

$s$ to be the sum of the elements of $Q'$

$P \oplus Q'$ to be the multiset union of $P$ and $Q'$

There is a bijection between subsets of $P \cup Q$ with sum $\alpha$, and subsets of $P \oplus Q'$ with sum $(\alpha + s)$, by replacing the elements selected from $Q$ with the negatives of the elements from $Q$ not selected.

By construction, $P \oplus Q'$ has only positive elements, and its subsets with sum $\alpha+s$ (or any other fixed sum) form an antichain. Sperner's theorem is that the cardinality of an antichain is at most $n \choose \lfloor \frac{n}{2} \rfloor$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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