A MINIMUM PROBLEM FOR FINITE SETS OF REAL NUMBERS WITH NON-NEGATIVE SUM

NEW

Problem: Reconstructed statement: for $n\ge1$ and $1\le r\le n$, let $N(a)$ be the number of nonempty subsets $S\subseteq[n]$ such that $\sum_{i\in S}a_i\ge0$, where exactly $r$ of the $a_i$’s are nonnegative and the remaining $n-r$ are negative, with $\sum_i a_i\ge0$. Let $\gamma(n,r)$ and $\eta(n,r)$ be the minimum and maximum possible values of $N(a)$. The conjecture asks whether every integer $q\in[\gamma(n,r),\eta(n,r)]$ is attained.

The intended count is of nonempty subset sums; otherwise the stated maximum $2^n-1$ in the source would be impossible. Also, for $r=n$, the definition gives $\gamma(n,n)=\eta(n,n)=2^n-1$, so that case is trivial.

Result: The conjecture is true.

For $r=n$, choose all $a_i>0$; every nonempty subset sum is nonnegative, so the only value is $2^n-1$.

Assume $1\le r<n$, and put $m=n-r$. It is known, and also follows directly, that

$$\gamma(n,r)=2^{n-1},\qquad \eta(n,r)=2^n-2^m .$$

Choose positive numbers

$$p_1,\dots,p_r,\ b_1,\dots,b_m$$

with $\sum_i p_i=\sum_j b_j$, and such that the signed vector

$$a^0=(p_1,\dots,p_r,-b_1,\dots,-b_m)$$

has no zero subset sum except the empty set and the full set. Such a choice exists: take $p_1,\dots,p_r,b_1,\dots,b_{m-1}$ positive and $\mathbb Q$-linearly independent with $\sum p_i>\sum_{j<m}b_j$, then set $b_m=\sum p_i-\sum_{j<m}b_j$.

For this initial vector, the total sum is $0$. Every proper nonempty subset $S$ pairs with its complement $S^c$, and their sums are nonzero opposites. Hence exactly one of each complementary pair is nonnegative, while the full set is also nonnegative. Therefore

$$N(a^0)=\frac{2^n-2}{2}+1=2^{n-1}.$$

Now increase only the positive coordinates:

$$a_i(t)=p_i+t c_i\quad(1\le i\le r),\qquad a_{r+j}(t)=-b_j\quad(1\le j\le m),$$

where $c_i>0$ are chosen generically. For each subset $S$ containing at least one positive coordinate, its sum is affine increasing in $t$. Purely negative subsets remain negative forever.

For each initially negative mixed subset $S$, there is a unique crossing time

$$\tau_S=\frac{-\sum_{i\in S}a_i^0}{\sum_{i\in S\cap[r]}c_i}>0.$$

Because there are only finitely many such subsets, the $c_i$’s may be chosen outside finitely many hyperplanes so that all $\tau_S$ are distinct. Then as $t$ increases, the count $N(a(t))$ starts at $2^{n-1}$ and rises by exactly $1$ at each crossing.

For sufficiently large $t$, every subset containing at least one positive coordinate has nonnegative sum, and every nonempty purely negative subset remains negative. Thus

$$N(a(t))=(2^r-1)2^m=2^n-2^m=\eta(n,r).$$

Since the count increases one at a time from $\gamma(n,r)$ to $\eta(n,r)$, every integer $q$ in that interval is attained.

Audit: the construction keeps exactly $r$ positive entries and $m$ negative entries, keeps the total sum nonnegative for all $t\ge0$, counts nonempty indexed subset sums, handles $r=n$ separately, and realizes exactly the required $q$.

Citation: Problem source: G. Chiaselotti, G. Marino, C. Nardi, “A minimum problem for finite sets of real numbers with non-negative sum,” arXiv:1102.4761. The proof above gives a complete resolution of P2.