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

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.