Given is an integer $n\ge 2$ and two rows of $n$ positive real numbers each, with each number not more than $n-0.5$, such that the numbers in each row sum to $n$. Is it always possible to choose some numbers such that from each row, at least one but not all numbers are chosen, and the sum of the chosen numbers is not less than $n-0.5$ but not more than $n+0.5$?

For example, with $n=2$ let the numbers in the first row be $a_1,a_2$ and in the second row $b_1,b_2$, where $a_1+a_2=b_1+b_2=2$ and (without loss of generality) $a_1\geq a_2$ and $b_1\geq b_2$. Then $1\leq a_1\leq 1.5$ and $0.5\leq b_2\leq 1$, meaning that $1.5\leq a_1+b_2\leq 2.5$ and giving us the conclusion.


The answer is Yes, and it follows from the following claim:

Claim. There exist two non-empty subsets $A\subsetneq \{a_1,\dots a_n\}$ and $B\subsetneq \{b_1,\dots b_n\}$ such that $|sum(A)-sum(B)|\leq 0.5$.

Indeed, replacing the set $A$ with $B$ in the sum $a_1+\dots+a_n$ results in the sum in the interval $[n-0.5,n+0.5]$.

Proof of claim. To prove the claim let's assume that $a_1 \leq a_2\leq \dots \leq a_n$ and $b_1 \leq b_2\leq \dots \leq b_n$. Then it's easy to see that $a_1\leq 1$ and $b_1\leq 1$. If they both do not exceed $0.5$ or both are above $0.5$, the claim holds for $A=\{a_1\}$ and $B=\{b_1\}$.

Without loss of generality it remains to consider the case $b_1\leq 0.5 < a_1$. Clearly, we have $1<b_n\leq n-0.5$. The following lemma implies that we can take $B=\{b_n\}$ and some $A$ whose sum is within distance $0.5$ from $b_n$. QED

Lemma. For any $n\geq 2$, and real numbers $\frac{1}{2}\leq a_1 \leq a_2\leq \dots \leq a_n$ with $a_1+\dots +a_n=n$, the sums of proper subsets of $\{a_1,\dots a_n\}$ form a $0.5$-covering of the interval $[0.5,n-0.5]$.

Proof of lemma. Proof is done by induction on $n$. The statement is trivial for $n=2$. Suppose that the statement holds for all $n\leq m$. Let us prove it for $n=m+1$.

So, for $\frac{1}{2}\leq a_1 \leq a_2\leq \dots \leq a_{m+1}$ with $a_1+\dots +a_{m+1}=m+1$, we need to show that any $t\in[0.5,m+0.5]$ is within distance $0.5$ from the sum of some proper subset of $\{a_1,\dots,a_{m+1}\}$. If $t>\frac{m+1}2$, we replace it with $m+1-t$ (covered by the complement of what covers $t$), and so we assume that $t\leq\frac{m+1}{2}$.

Clearly, we have $a_{m+1}>1$, and thus $$s:=\sum_{i=1}^m a_i = m+1-a_{m+1} < m.$$ We also have $s\geq a_1m \geq \frac{m}{2}$.

Define $t':=t\frac{m}{s}$ and notice that $0.5\leq t<t'\leq \frac{(m+1)m}{2s}\leq m+\frac{m}{2s}$. For $i=1,2,\dots,m$, define $a'_i:=a_i\frac{m}{s}$, which sum to $m$ and have $a'_1\geq a_1\geq \frac12$.

Consider two cases:

  • Case 1. If $t'\leq m-0.5$, then by induction, there exists a non-empty subset $J\subsetneq\{1,2,\dots,m\}$ such that $$|\sum_{j\in J} a'_j - t'|\leq 0.5.$$ Multiplying by $\frac{s}{m}$, we get $$|\sum_{j\in J} a_j - t|\leq 0.5\frac{s}{m} \leq 0.5.$$

  • Case 2. If $m-0.5 < t' \leq m+\frac{m}{2s}$, we set $J:=\{1,2,\dots,m\}$ giving the same inequality as above.



For what it worth, the lemma from the nice answer by Max Alekseyev may be deduced from the following general (and I guess well known, but do not remember a specific reference)

Claim. If $a$ and $a_1\leqslant a_2\leqslant \ldots \leqslant a_n$ are positive numbers satisfying $a_j\leqslant a_1+a_2+\ldots+a_{j-1}+a$ for all $j=1,2,\ldots,n$, then in the multiset of $2^n$ partial sums $A:=\{\sum_{i\in I} a_i:I\subset \{1,2,\ldots,n\}\}$ any two consecutive elements differ at most by $a$.

Proof. Induction in $n$.

Base $n=1$ is clear: $A$ contains two elements $0$ and $a_1$, the difference does not exceed $a$.

Step from $n-1$ to $n$. Denote $B:=\{\sum_{i\in I} a_i:I\subset \{1,2,\ldots,n-1\}\}$, then $A=B\cup (B+a_n)$, $\min(B+a_n)=a_n\leqslant \max(B)+a$, thus indeed any two consecutive elements of $A$ differ at most $a$.

Now if $1/2\leqslant a_1\leqslant\ldots \leqslant a_n$ and $a_1+\ldots+a_n=n$, the condition of claim holds with $a=1$. Indeed, if $a_j> a_1+\ldots+a_{j-1}+1$ for certain $j\in \{1,\ldots,n\}$, then $$a_1+\ldots+a_n> (j-1)\cdot\frac12+(n-j+1)\cdot \frac{j+1}2=n+\frac{(j-1)(n-j)}2\geqslant n,$$ a contradiction.

  • $\begingroup$ Thanks for the pointer! This general lemma is very elegant. $\endgroup$ – Max Alekseyev Dec 18 '19 at 3:18

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.