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.



Two rows of bounded numbers
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](https://en.wikipedia.org/wiki/Delone_set) 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.


QED


