I have a question about the answer given to this problem. The problem is reproduced below:
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.
The integers 1, 2, ..., 225 are arranged in a 15×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).
Please help me understand the logic behind the answer above. This is what I was not able to understand:
It is easy to see why there will be r * b 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 array and again find it to be red. We remove the column containing it and note that we have found a total of 2b purples so far. Each time we remove a column, we find the single largest colored box to be red and eventually discover r * b purples. This much I understood.
But, now, let us look at an alternate. In the same 15 * 15 array, we find the largest single colored number to be red. We count 5 purples and remove the column containing it, leaving us with a 15 * 14 array. Now, in this 15 * 14 array we find the largest single colored number to be blue. Removal of the row containing this blue box can only guarantee giving us 4 purples.
My question then is, 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?