What is the greatest cardinality of a set $S$ of positive integers strictly less than $k$ such that no subset of $S$ sums to $k$, in terms of $k$?

I worked this out for small values of $k$, and realized that a lower bound for the cardinality of $S$ is $\lfloor \frac{k}{2} \rfloor$, as one can select $S$ to be the set of integers $n$ such that $\frac{k}{2} \le n \lt k$ (and then any value of $n \lt \frac{k}{2}$ would have a corresponding element of $S$ equal to $k-n$ for which the sum is $k$), but I want to know if there is a better bound, and if so, how to show that it holds. (For the record, I don’t think that one exists, but I don’t know how to prove that.)

  • 2
    $\begingroup$ Ignoring rounding, there are about $\frac k2$ pairs which sum to $k$. You can't choose both members from any pair, so... $\endgroup$ – lulu Oct 6 at 21:22
  • $\begingroup$ Can you improve your problema statement, please? "$\forall A\subset S: ~ \sum_{i\in A} i \neq k$ ...." or " $\sum_{i\in S} i\neq k$" ? $\endgroup$ – Alexandre Frias Oct 6 at 22:01
  • $\begingroup$ For some set of numbers less than $k$, no subset of that set sums to $k$. Is that clear? $\endgroup$ – Lieutenant Zipp Oct 6 at 23:26

Your Answer

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

Browse other questions tagged or ask your own question.