# Show there’s 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$

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!

• 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. – 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$.