i tried to find a simple postable,readable solution but i don't think i was able to do better than this; suppose the numbers in the first row are $a_1,a_2,\ldots a_n$ in descending order. also assume that $a_1,a_2,\ldots,a_m\geq 1/2;a_{m+1},\ldots,a_n<1/2$. wlog $m\leq n/2$ else we flip the two rows. suppose $k$ is an integer such that $|k-\sum a_i|\leq 1/2$. if we choose $k$ terms from the second row and $n-k$ from the first and let the row sums of the chosen elements be $r_1,r_2$ then we have $|r_1-r_2|\leq 1/2$. if further $r_1+r_2\leq n/2$ then we are through since if say $r_1\geq r_2$ then we have $r_1-r_2\leq 1/2,r_1+r_2\leq n/2\Rightarrow 2r_1\leq (n+1)/2$. now firstly note that $k-1/2\leq \sum a_i = \sum_{i=1}^m a_i+\sum_{i=m+1}^n a_i < m+(n-m)/2=(n+m)/2$ so that $2k\leq m+n$. we claim that the following choice for the two rows is good: row 1 : $a_{k+1},a_{k+2},\ldots,a_n$ row 2 : $1-a_1,1-a_2,\ldots,1-a_k$. now firstly if $k\geq m$ then note that we have the following situation: Row 1: $a_1\geq\cdots\geq a_{2k-n}\geq \overbrace{a_{2k-n+1}\geq\cdots a_m\geq \cdots\geq a_k}\geq \overbrace{a_{k+1}\geq \cdots\geq a_n}$; ( the number of terms is $n-k$ in both) Row 2: $(1-a_1)\leq (1-a_2)\leq\cdots\leq (1-a_{2k-n})\leq \underbrace {(1-a_{2k-n+1})\leq\cdots\leq (1-a_m)\leq\cdots\leq (1-a_k)}\leq\underbrace{(1-a_{k+1})\leq\cdots\leq (1-a_n)}$ now it is easy to see that the sum of the terms included in $r_1+r_2$ is $\leq$ the terms that are not included in this sum(the terms $a_{2k-n+1},\ldots a_k$ dominate the terms $a_{k+1},\ldots,a_n$;a likewise thing for the terms of row 2; finally $\forall i\in \{1,2,\ldots,2k-n\}, 1-a_i\leq a_i$ so that the claim is verified) and since sum of all the terms is $n$, it follows that $r_1+r_2\leq n/2$ as required. if $m>k$ then note that the terms $a_i\geq 1-a_i ,i \in\{1,2,\ldots,2k-m\}$; also $a_i,i\in \{2k-m+1,\ldots,k\}$ dominate over the terms $a_i,i \in \{k+1,\ldots,m\}$; finally for $i>m, a_i<1-a_i$ and so the above inequality,$r_1+r_2\leq n/2$ is satisfied again.

grobber wrote: In a $2\times n$ array we have positive reals s.t. the sum of the numbers in each of the $n$ columns is $1$. Show that we can select a number in each column s.t. the sum of the selected numbers in each row is at most $\frac{n+1}4$. Here is my solution: We denote the numbers from the first row by $a_1$, $a_2$, ..., $a_n$ in increasing order: $a_1\leq a_2\leq ...\leq a_n$. Then, the corresponding numbers from the second row are obviously $1-a_1$, $1-a_2$, ..., $1-a_n$. Now, let $k$ be the largest index satisfying $a_1+a_2+...+a_k\leq\frac{n+1}{4}$. We WLOG assume that $k \neq n$ (since otherwise, we can simply select all numbers from the first row and no numbers from the second row, and we are done). Thus, $k+1 \leq n$, so that $a_{k+1}$ is well-defined. Moreover, $a_1+a_2+...+a_{k+1}>\frac{n+1}{4}$ (since $k$ was chosen to be the largest index satisfying $a_1+a_2+...+a_k\leq\frac{n+1}{4}$). Now, we are going to prove that $\left(1-a_{k+1}\right)+\left(1-a_{k+2}\right)+...+\left(1-a_n\right)\leq\frac{n+1}{4}$. In fact, recall that $a_1\leq a_2\leq ...\leq a_n$. Hence, the arithmetic mean of the numbers $a_{k+1}$, $a_{k+2}$, ..., $a_n$ is greater or equal than the number $a_{k+1}$ (the smallest of the numbers $a_{k+1}$, $a_{k+2}$, ..., $a_n$). In other words, $\frac{a_{k+1}+a_{k+2}+...+a_n}{n-k}\geq a_{k+1}$. On the other hand, recall again that $a_1\leq a_2\leq ...\leq a_n$. Hence, the arithmetic mean of the numbers $a_1$, $a_2$, ..., $a_{k+1}$ is smaller or equal than the number $a_{k+1}$ (the greatest of the numbers $a_1$, $a_2$, ..., $a_{k+1}$). In other words, $\frac{a_1+a_2+...+a_{k+1}}{k+1}\leq a_{k+1}$. Thus, $\frac{a_{k+1}+a_{k+2}+...+a_n}{n-k}\geq a_{k+1} \geq \frac{a_1+a_2+...+a_{k+1}}{k+1}$, and thus $a_{k+1}+a_{k+2}+...+a_n\geq\left(n-k\right)\cdot\frac{a_1+a_2+...+a_{k+1}}{k+1} \geq \left(n-k\right)\cdot\frac{\left(\frac{n+1}{4}\right)}{k+1}$ (since $n-k\geq 0$ and $a_1+a_2+...+a_{k+1}>\frac{n+1}{4}$). In other words, $a_{k+1}+a_{k+2}+...+a_n\geq \left(n-k\right)\cdot\frac{\left(\frac{n+1}{4}\right)}{k+1} = \frac{\left(n+1\right)\left(n-k\right)}{4\left(k+1\right)}$. Hence, $\left(1-a_{k+1}\right)+\left(1-a_{k+2}\right)+...+\left(1-a_n\right)$ $=\left(n-k\right)-\left(a_{k+1}+a_{k+2}+...+a_n\right)\leq\left(n-k\right)-\frac{\left(n+1\right)\left(n-k\right)}{4\left(k+1\right)}$. Thus, in order to show that $\left(1-a_{k+1}\right)+\left(1-a_{k+2}\right)+...+\left(1-a_n\right)\leq\frac{n+1}{4}$, it will be enough to prove that $\left(n-k\right)-\frac{\left(n+1\right)\left(n-k\right)}{4\left(k+1\right)}\leq\frac{n+1}{4}$. This, however, is straightforward: $\left(n-k\right)-\frac{\left(n+1\right)\left(n-k\right)}{4\left(k+1\right)}\leq\frac{n+1}{4}\ \ \ \ \ \Longleftrightarrow\ \ \ \ \ n-k\leq\frac{n+1}{4}+\frac{\left(n+1\right)\left(n-k\right)}{4\left(k+1\right)}$ $\Longleftrightarrow\ \ \ \ \ n-k\leq\frac{n+1}{4}\left(1+\frac{n-k}{k+1}\right)\ \ \ \ \ \Longleftrightarrow\ \ \ \ \ n-k\leq\frac{n+1}{4}\cdot\frac{n+1}{k+1}$ $\Longleftrightarrow\ \ \ \ \ n-k\leq\left(\frac{n+1}{2}\right)^2\cdot\frac{1}{k+1}\ \ \ \ \ \Longleftrightarrow\ \ \ \ \ \left(n-k\right)\left(k+1\right)\leq\left(\frac{n+1}{2}\right)^2$. But this is clear from AM-GM: $\left(n-k\right)\left(k+1\right)\leq\left(\frac{\left(n-k\right)+\left(k+1\right)}{2}\right)^2 = \left(\frac{n+1}{2}\right)^2$. So we have proved the inequality $\left(1-a_{k+1}\right)+\left(1-a_{k+2}\right)+...+\left(1-a_n\right)\leq\frac{n+1}{4}$. Together with $a_1+a_2+...+a_k\leq\frac{n+1}{4}$, this shows that if we choose the numbers $a_1$, $a_2$, ..., $a_k$ from the first row and the numbers $1-a_{k+1}$, $1-a_{k+2}$, ..., $1-a_n$ from the second row, then the sum of the chosen numbers in each row is $\leq\frac{n+1}{4}$. And the problem is solved. Unrelated to my solution above, here is a question on seshadri's solution: In the case $k\geq m$, how do we make sure that $k\geq n/2$ (we need this to speak of $a_{2k-n+1}$)? Maybe $m\leq n/2$ should be replaced by $m\geq n/2$ ? In this case, seshadri's solution seems to work (one minor mistake, though: the proof of $2k\leq n+m$ does not work in the special case when $n=m$, because we get a $\leq$ sign instead of the $<$ sign in $k-1/2\leq \sum a_i = \sum_{i=1}^m a_i+\sum_{i=m+1}^n a_i < m+(n-m)/2=(n+m)/2$; but fortunately there is an easy reason why $2k\leq n+m$ holds in the case when $n=m$). Darij

I've got this solution just few minutes ago..... Assume the numbers in first row are $a_i's$ with non decreasing order , similarly define $b_i's$ for second row. Let $k$ be the least such that $\sum_{r=1}^{k} a_r >\frac {n+1}{4}$ Now $a_k\geq \frac {\sum_{r=1}^{k} a_r }{k}>\frac {n+1}{4k}$ Now $\sum_{r=k}^{n}b_r\leq (n+1-k)(b_k)<(n+1-k)(1-\frac {n+1}{4k})=x$ Now note $x=\frac {5}{4}(n+1)-\frac {(n+1)^2+4k^2}{4k}\leq \frac {5}{4}(n+1)-\frac {4k(n+1)}{4k}=\frac {n+1}{4}$ Also by our assumption we had $\sum_{r=1}^{k-1}a_i\leq \frac {n+1}{4}$. So done.

it can be done beautifully by greedy algorithm just take the row with the less sum and add it's min to it

$ x=\frac{5}{4}(n+1)-\frac{(n+1)^2+4k^2}{4k}\leq\frac{5}{4}(n+1)-\frac{4k(n+1)}{4k}=\frac{n+1}{4} $

Sort the array by the top entry. Let the top entries form the non-decreasing sequence $(a_i)$. Let the corresponding bottom entries form the sequence $(b_i)$. Consider $k$ such that $$\sum_{i=1}^{k} a_i \leq \frac{n+1}{4} \text{ and } \sum_{i=1}^{k+1} a_i > \frac{n+1}{4}$$It follows that $a_{k+1}> \frac{n+1}{4(k+1)}$ implying that $b_{k+1}<\bigg(1-\frac{n+1}{4(k+1)}\bigg)$. Since for any $m\geq k+1$ we have that $b_m\leq b_{k+1}$, it suffices to show that $$(n-k)\bigg(1-\frac{n+1}{4(k+1)}\bigg)\leq \frac{n+1}{4}$$Expanding and simplifying, we have see that it suffices to show that $$(n-2k)(n-2k-2)+1\geq 0$$Considering the cases $n-2k=1$, $n-2k=0$, $n-2k<0$ and $n-2k>0$ gives the desired result. $\square$

Let $x_1,\ldots,x_n$ be the numbers in the top row. Our goal is to show that there is some $I\subset[n]$ such that \[\sum_{i\in I}x_i\le\frac{n+1}{4}\]and \[\sum_{i\not\in I}(1-x_i)\le\frac{n+1}{4}.\]WLOG suppose $x_1\le x_2\le\cdots\le x_n$. Then, pick $I=[m]$ where $m$ is the index such that \[x_1+\cdots+x_m\le\frac{n+1}{4}\quad\text{ and }\quad x_1+\cdots+x_{m+1}>\frac{n+1}{4}.\]If this index does not exist, then $I=[n]$ works just fine. Remark: This is basically greedy algorithm. In fact, it is easy to show that this is forced, but we omit it for brevity. We claim that $I=[m]$ works. Indeed, $\sum_{i\in I}x_i\le\frac{n+1}{4}$ by construction, so it suffices to show that $\sum_{i\not\in I}(1-x_i)\le\frac{n+1}{4}$. We see that \[(m+1)x_{m+1}\ge x_1+\cdots+x_{m+1}>\frac{n+1}{4},\]so $x_{m+1}>\frac{n+1}{4(m+1)}$. Note that $x_i\ge x_{m+1}>\frac{n+1}{4(m+1)}$ for $i\ge m+1$, so \[S:=(1-x_{m+1})+\cdots+(1-x_n)\le(n-m)(1-x_{m+1})<(n-m)\left(1-\frac{n+1}{4(m+1)}\right).\]Let $k=\frac{m+1}{n+1}$. Then, we have \[S<(n+1)(1-k)\left(1-\frac{1}{4k}\right)=(n+1)\left(\frac{5}{4}-k-\frac{1}{4k}\right)\le\frac{n+1}{4},\]where the last step is by AM-GM. Thus, we have $S\le\frac{n+1}{4}$, so the proof is complete.

Let the numbers in the top row be $a_1 \le \cdots \le a_n$. We will choose $a_1,\ldots,a_k$ in the first row, such that \[ a_1+\cdots+a_k \le \frac{n+1}{4}, \qquad a_1+\cdots+a_{k+1} >\frac{n+1}{4}. \]We want to show $(1-a_{k+1})+\cdots+(1-a_n) \le \tfrac{n+1}{4}$. Note \[ (1-a_{k+1})+\cdots+(1-a_n) \le (n-k)(1-a_{k+1}),\]so we want to show \[ a_{k+1} \ge 1-\frac{n+1}{4(n-k)}. \]We have \[ (k+1)a_{k+1} \ge a_1+\cdots+a_{k+1} > \frac{n+1}{4} \implies a_{k+1} > \frac{n+1}{4(k+1)}. \]Now it suffices to show \[ \frac{n+1}{4(k+1)} \ge 1-\frac{n+1}{4(n-k)}, \text{ i.e. } (n+1)^2 \ge 4(k+1)(n-k),\]which is true by AM-GM.

Let the numbers in the top row be \(a_1\le a_2\le\cdots\le a_n\) and let the numbers in the bottom row be \(1-a_1\), \(1-a_2\), \(\ldots\), \(1-a_n\). Consider the index \(k\) with the property that \[a_1+\cdots+a_k\le\tfrac{n+1}4<a_1+\cdots+a_{k+1}.\]Then it follows that \begin{align*} (1-a_{k+1})+\cdots+(1-a_n) &\le(n-k)(1-a_{k+1})\\ &\le(n-k)\left(1-\frac{n+1}{4(k+1)}\right)\le\frac{n+1}4, \end{align*}where the last inequality holds since \[\frac{n+1}{4(n-k)}+\frac{n+1}{4(k+1)}\ge1.\]

We sort the top row in ascending order, and denote them $a_1<a_2<a_3<\cdots < a_n$. Assume $A$ satisfies \[\sum_{i=1}^A a_i > \frac{n+1}{4}\]This implies $A\cdot a_A > \frac{n+1}{4}$ as well, and by extension $b_A < 1 - \frac{n+1}{4A}$. Then, we note that \begin{align*} \sum_{i=A}^n b_i &< (n-A+1) b_A\\ &<((n+1)-A) \left(1- \frac{n+1}{4A}\right)\\ % &= \frac{1}{4A} ((n+1)-A)(4A - (n+1)) &= (n+1) - A - \frac{(n+1)^2}{4A} + \frac{n+1}{4}\\ &= -\frac{((n+1) + 2A)^2}{4A} + \frac{n+1}{4}\\ &< \frac{n+1}{4} \end{align*}Thus, if we select the largest $X$ such that $\sum_{i=1}^X a_i< \frac{n+1}{4}$, then $\sum_{j=1}^{X+1} b_i< \frac{n+1}{4}$, so we have select the $a$ in the first $X$ columns, and $b$ in the last $n-X$ columns, and the sum in each row will always be $< \frac{n+1}{4}$.

Suppose in the top row our numbers are $a_1\le a_2\le\dots\le a_n$. Let $m$ be the index such that \[a_1+\dots+a_m\le\frac{n+1}{4}<a_1+\dots+a_{m+1}\]It suffices to show \[(1-a_{m+1})+(1-a_{m+2})+\dots+(1-a_n)\le\frac{n+1}{4}\]Notice that \[a_{m+1}\ge\frac{a_1+\dots+a_{m+1}}{m+1}>\frac{n+1}{4(m+1)}\]so \[(1-a_{m+1})+\dots+(1-a_n)\le (n-m)-\frac{(n-m)(n+1)}{4(m+1)}\le\frac{n+1}{4}\]by expanding and using AM-GM. $\square$

$\color{blue} \boxed{\textbf{SOLUTION}}$ Let $a_1 \le a_2 ... \le a_n, b_1\ge b_2... \ge b_n$ be the numbers in column $1$ to $n$ There exist some $k$ for which $$\sum_{i=1}^k a_i \le \frac{n+1}{4}$$But $$\sum_{i=1}^{k+1} a_i >\frac{n+1}{4}$$ $$a_{k+1} \ge \frac{\sum_{i=1}^{k+1} a_i}{k+1} > \frac{n+1}{4(k+1)}$$ $$\sum_{i=k+1}^n b_i < b_{k+1}(n-k) < (1-a_{k+1})(n-k)$$ We need to show, $$\left(n-k\right)-\frac{\left(n+1\right)\left(n-k\right)}{4\left(k+1\right)}\leq\frac{n+1}{4}$$ Which is true because - $$ n-k\leq\frac{n+1}{4}\left(1+\frac{n-k}{k+1}\right)\ \ \ \ \ \Longleftrightarrow\ \ \ \ \ n-k\leq\frac{n+1}{4}\cdot\frac{n+1}{k+1} \Longleftrightarrow\ \ \ \ \ n-k\leq\frac{n+1}{4}\cdot\frac{n+1}{k+1} \Longleftrightarrow\ \ \ \ \ n-k\leq\left(\frac{n+1}{2}\right)^2\cdot\frac{1}{k+1}\ \ \ \ \ \Longleftrightarrow\ \ \ \ \ \left(n-k\right)\left(k+1\right)\leq\left(\frac{n+1}{2}\right)^2$$ This is true by $\textbf{AM-GM Inequality}$ $$\left(n-k\right)\left(k+1\right)\leq\left(\frac{\left(n-k\right)+\left(k+1\right)}{2}\right)^2 = \left(\frac{n+1}{2}\right)^2 \blacksquare$$

Here's a pretty insane greedy solution. We do the following: in the beginning, no columns are crossed out. We select the smallest number not crossed out on the array, providing that this does not violate the condition. Then we cross out the column that number is in. At some point, this process must terminate, i.e. selecting the smallest remaining number will cause the corresponding row to have a sum greater than $\frac{n+1}4$. It follows that before that number was selected, the sum of that row $r$ is greater than $\frac{n-1}4$, as the selected number is at most $\frac 12$. Suppose that, at this point, $k$ numbers were selected in $r$. Then, consider the remaining $n-k$ columns (note that some of the columns may be crossed out already, but that doesn't matter). Suppose for the sake of contradiction that the numbers in those $n-k$ columns $c_1, c_2, \dots, c_{n-k}$ not in $r$ sum to more than $\frac{n+1}4$. Then, the numbers in the $c_i$ in row $r$ must sum to less than $n-k-\frac{n+1}4$. However, note that by our greedy choice, in row $r$, every element that is in a column $c_i$ must be greater than any element that is not in any of the $c_i$; otherwise, we would have chosen the element in $c_i$ over that other element. Let $C$ be the set of $c_i$. It follows that we have the inequality $$\frac{n-1}{4k} < \operatorname{Avgnum}(\overline C) < \operatorname{Avgnum}(C) < 1-\frac{n+1}{4k}.$$This simplifies to $$k(n-k)(2k-n)(2k-n+1) > 0,$$i.e. $\frac {n-1}2 < k < \frac n2$. There is no integer in that open interval, hence contradiction.

Order the top row so that the numbers are in increasing order and are $a_1 , a_2 ... , a_n$. The algorithm is that we choose $a_1,a_2 ... a_r$ till the sum is $\le \frac{n+1}{4}$ and $a_1+ a_2 ... + a_r + a_{r+1} > \frac{n+1}{4}$. We claim that this algorithm works. So we need to show $$n-r - a_{r+1} - a_{r+2} ... - a_{m} \le \frac{n+1}{4} \iff a_{r+1} + a_{r+2} ... + a_{m} > \frac{3n-4r-1}{4}$$For the sake of contradiction assume otherwise. We have $$ a_r(n-r) \le a_{r+1} + a_{r+2} ... + a_{m} < \frac{3n-4r-1}{4}$$and $$a_{r+1} > \frac{n+1}{4} - a_1 ... - a_r \ge \frac{n+1}{4} - a_r r \Rightarrow \frac{3n-4r-1}{4} > (n-r)(\frac{n+1}{4} - a_r r) $$Isolating $a_r$ on both inequalities gives $$\frac{n^2 - 2n +3r-rn+1}{4r(n-r)} < a_r \le \frac{3n-4r-1}{4(n-r)} \Rightarrow n^2 -2n +4r -4rn + 4r^2 + 1 = (n - 2r - 1)^2 < 0$$which is a contradiction.

Let the numbers on the top row be $a_1, a_2, \cdots, a_n,$ and the sum of the chosen numbers of the top and bottom row be $S_1, S_2$ respectively. WLOG, assume that $a_1 \leq a_2 \leq \dots \leq a_n.$ We chose the numbers as follows. We first find the greatest positive integer $k$ such that $a_1+a_2+\cdots+a_k \leq \frac{n+1}{4}.$ Then we choose all of these numbers, so $S_1=a_1+a_2+\cdots+a_k \leq \frac{n+1}{4}.$ Then, we take all the other columns and choose their bottom number, thus $$S_2=(1-a_{k+1})+(1-a_{k+2})+\cdots+(1-a_n) \geq n-k-(n-k)a_k = (n-k)(1-a_k).$$However, note that each of $a_1, a_2, \dots, a_k$ are less than or equal to $a_k,$ so to minimize $k$ we would need all of them to equal $a_k.$ Therefore $$\displaystyle k \geq \left \lceil \frac{\frac{n+1}{4}}{a_k} \right \rceil \geq \frac{n+1}{4a_k}.$$Hence, $$S_2 \leq \left( n-\frac{n+1}{4a_k} \right)(1-a_k) = n+\frac{n+1}{4}-\left( \frac{n+1}{4a_k}+na_k \right) \leq \frac{n+1}{4}+n-2\sqrt{\frac{n(n+1)}{4}}$$by AM-GM. However, we then have $$S_2 \leq \frac{n+1}{4}+n-2\sqrt{\frac{n(n+1)}{4}} < \frac{n+1}{4}+n-n=\frac{n+1}{4}.$$Thus $S_1, S_2 \leq \frac{n+1}{4},$ so we are done. QED