6
$\begingroup$

In a matrix with $a$ rows and $2b+1$ columns, each cell contains a nonnegative real number. Does there exist a fixed $k>0$, independent of $a$ and $b$, for which we can always choose a set of columns $C$, with $|C|=c\in [1,2b]$, so that

  • For at least $k\cdot a$ rows, the sum of the $c$ numbers in each row is at least the sum of any other $2b-c$ (out of the remaining $2b+1-c$) numbers in the same row

  • For at least $k\cdot a$ rows, the sum of the remaining $2b+1-c$ numbers in each row is at least the sum of any other $c-1$ (out of the original $c$) numbers in the same row?

If we have only the first condition, an averaging argument using $c=b$ gives us that $k\geq 1/4$. But with the second condition also imposed, it doesn't look like the averaging argument still works.

$\endgroup$
  • $\begingroup$ I don't think the edited version is true. For example, take $a=1,b=2$ with matrix $[1,0,0,0,0]$. $\endgroup$ – Tengu Jul 19 '18 at 14:55
  • $\begingroup$ Right, just edited. Last try now. $\endgroup$ – Karo Jul 20 '18 at 20:53
1
$\begingroup$

For the matrix [1 2 4] , $(a=1,b=1)$, you must choose third column to satisfy the first condition but then second condition isn't satisfied. So you can choose $0$ rows which satisfy both conditions but that is less than $k\cdot a$ for any $k>0$

So answer is no.

$\endgroup$
  • 1
    $\begingroup$ You're right - the second condition was not what I wanted. I just edited. Sorry about this. $\endgroup$ – Karo Jul 16 '18 at 22:05

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.