Given a table with $a$ rows and $2b+1$ columns. Each cell contains a nonnegative real number. What is the largest number $k\in[0,1)$, independent of $a$ and $b$, for which we can always choose $b$ columns so that for at least $k\cdot a$ rows, the sum of the $b$ numbers in each row is at least the sum of any other $b$ (out of the remaining $b+1$) numbers in the same row?
Example: Suppose we have a table corresponding to the $3\times 3$ identity matrix. Then no matter which column we choose, the condition is only satisfied for one of the three rows. This shows that the largest $k$ is no more than $1/3$. Is $1/3$ the largest possible $k$?
An averaging argument should work. For now, I prove that $k=1/4$ is possible.
Claim: If a random set of $b$ columns is picked, then for a given row, the probabiity that this set is good is at least $\dfrac{(b+1)}{(4b+2)} > 1/4$. This implies that there must be $b$ columns which are good for at least $1/4$ fraction of the rows. Thus, $k \geq 1/4$.
Proof of claim: For a set $I$ of $b$ columns and a row $r$, let $E(r,I)$ be the desired event: the sum of the $b$ numbers indexed by $r$ and $I$ is at least the sum of any other $b$ elements (of the remaining $b+1$) in the same row.
Let $F(r,I)$ be the event that the smallest element in the row $r$ is in one of the columns indexed by $\{1,2,\ldots,2b+1\} \setminus I$.
Pick $I$ uniformly at random. Then, conditioned on $F(r,I)$, the probability of $E(r,I)$ is $1/2$ because $E(r,I)$ happens when the sum of the $b$ elements indexed by $I$ is at least the sum of the $b$ elements indexed by $\{1,2,\ldots,2b+1\}$ (excluding the index of the smallest element). Note that conditioning still gives a uniformly random partition of the remaining $2b$ elements.
The probability of $F(r,I)$ is clearly at least $\dfrac{(b+1)}{(2b+1)}$, which completes the proof of the claim.