Given a set of n real numbers, if the sum of the elements of every subset of size larger than k is negative, what is the maximum number of subsets of nonnegative sum? In this note we show that the answer is (n-1/k-1) + (n-1/k-2) + • • • + (n-1 0 )+ 1, settling a problem of Tsukerman. We provide two proofs; the first establishes and applies a weighted version of Hall's theorem, and the second is based on an extension of the nonuniform Erd.os-Ko-Rado theorem.
|Original language||English (US)|
|Number of pages||6|
|Journal||SIAM Journal on Discrete Mathematics|
|State||Published - 2014|
All Science Journal Classification (ASJC) codes
- Hall's theorem
- Nonnegative subsets