# Coloring 5 Largest Numbers in Each Row and Column Yields at Least 25 Double-Colored Numbers

This is a question from a very old American Mathematical Monthly, if I recall correctly. It has a very nice solution and illustrates an often useful technique. If it is unsolved after a while, I will post a solution.

The integers $1,2,\ldots,225$ are arranged in a $15\times 15$ array. In each row, the five largest numbers are colored red, and in each column, the five largest numbers are colored blue. Prove that there are at least $25$ numbers colored both blue and red (purple, if you will).

Edit: Since there have been no attempts yet, I'll give a hint. Try to make the question "harder" first.

• Is it true that this works for an array of any size? – Jorge Dec 18 '13 at 23:25
• yes. you should try to relax all the conditions for this problem – cats Dec 19 '13 at 1:08
• So for the largest n of any column or row we have at least $n^2$ purple? – Jorge Dec 19 '13 at 1:15
• Yes. More generally, if you have an $m\times n$ array with the $r$ largest in each row and $b$ largest in each column, there are at least $rb$ purple. – cats Dec 19 '13 at 1:21
• Wow, I hadn't thought about that last one. Sweet. – Jorge Dec 19 '13 at 1:24

As mentioned in the hint, we will first generalize the question as follows. The integers $1, \ldots, mn$ are arranged in an $m\times n$ array. In each row, the $r \le n$ largest numbers are colored red, and in each column, the $b \le m$ largest numbers are colored blue. Prove that there are at least $rb$ numbers colored purple.
The proof of this is by strong induction on $m+n+r+b.$ Base cases are easy to check, so I will skip over them. Now, consider the largest single-colored number $x$ (if no such number exists, then we're obviously done). Without loss of generality, suppose $x$ is colored red. The column containing this number has $b$ numbers colored blue, none of which are $x,$ since $x$ is single-colored. But this means that all $b$ of these numbers are larger than $x,$ whence they must all be colored red by assumption. Hence, this column contains $b$ purple numbers.
Removing this column, we get an $m\times (n-1)$ array where in each row, at least $r-1$ of the largest numbers are colored red, and the $b$ largest numbers are colored blue in each column. By induction, this yields at least $(r-1)b$ purple numbers, so adding in the original $b$ gives $rb,$ as desired.
Remark: Some of you may notice that the generalized problem actually does not immediately give the result in the final paragraph, since in the subarray, we are not looking at the numbers $1,\ldots, m(n-1).$ This can be remedied easily by modifying the statement to be for $mn$ distinct real numbers.
• @HemantAgarwal: That’s why the argument uses induction: the induction hypothesis automatically ensures that the $m\times(n-1)$ array has $(r-1)b$ purple numbers. – Brian M. Scott Feb 20 at 8:25