12
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ Is it true that this works for an array of any size? $\endgroup$ – Jorge Dec 18 '13 at 23:25
  • $\begingroup$ yes. you should try to relax all the conditions for this problem $\endgroup$ – cats Dec 19 '13 at 1:08
  • $\begingroup$ So for the largest n of any column or row we have at least $n^2$ purple? $\endgroup$ – Jorge Dec 19 '13 at 1:15
  • 1
    $\begingroup$ 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. $\endgroup$ – cats Dec 19 '13 at 1:21
  • $\begingroup$ Wow, I hadn't thought about that last one. Sweet. $\endgroup$ – Jorge Dec 19 '13 at 1:24
5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ It is easy to see why there will be rb purples when all the boxes with the single largest color are of the same colour. What I mean is is that let's say that the largest single colored box is red. Then we remove the column containing it and note that we have found b purple boxes in that column . We look at the largest single colored box in the remaining columns and again find it to be red. We remove this column and note that we have found a total of 2b purples so far. We keep doing and eventually discover rb purples . This much I understood ..cont'd below $\endgroup$ – Hemant Agarwal Feb 2 at 12:54
  • $\begingroup$ But lets look at another case. The first largest single colored box is red and after we remove the column containing it, the largest single colored box in the remaining array is blue and so on. Basically, how do we go on to prove that we will still get r*b purple boxes even when all the single largest colored boxes after removing a column/row are not of the same colour. $\endgroup$ – Hemant Agarwal Feb 2 at 12:55
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Feb 20 at 8:25

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.