0
$\begingroup$

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).

Link to answer given

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?

$\endgroup$
0
1
$\begingroup$

The answer you're asking about doesn't in any way make the assumption you seem to be claiming it does.

In your "alternate" scenario:

  • We find the largest single-coloured number to be red. (OK so far.)
  • We count five purples in its column. (OK so far.)
  • We remove that column leaving a 15x14 array. (OK so far.)

But now you start asking "what if the largest single-coloured number in the reduced array is blue?" -- but none of the details of that reduced array matter at all. All that matters is that in the reduced array we can apply the induction hypothesis, which says that for smaller m+n+r+b (which we certainly have here) the original claim holds. That means that in our 15x14 array we have at least 20 purple numbers.

A proof by induction doesn't "care" why the induction hypothesis holds in simpler cases. The induction principle just says that under certain circumstances, when you're trying to prove something you're allowed to assume that it holds in all cases simpler than the one you're considering. E.g., here you're allowed to assume that the theorem is true for all situations with m+n+r+b smaller than what you started with.

And that's all you need. If you've got a 15x15 array with the given property for r=5,b=5, and there's a column with 5 purples in it such that removing it yields a 15x14 array with the given property for r=4,b=5 -- which there must be, and it seems you're happy with that bit of the proof -- then by induction you can assume that that array has 20 purples in it. Add those to the 5 purples in the column you removed and you've got 25 purples and you're done.

(If you're still not convinced, consider one way of seeing where the induction principle comes from. Suppose the theorem isn't always true, and consider a failing case where m+n+r+b is as small as possible. Then any smaller case satisfies the theorem, just because otherwise you'd have picked a different one when you looked for m+n+r+b as small as possible.)

$\endgroup$
14
  • $\begingroup$ This is becoming a chameleon question. Our model is one question per question - not "constantly changing question forcing answers to update". Main site is not chat, we don't do real-time help. $\endgroup$ – bobble Apr 9 at 2:04
  • $\begingroup$ @bobble apologies. I have reverted back to my original question and will seek clarification from Gareth here in the comments. $\endgroup$ – Hemant Agarwal Apr 9 at 3:39
  • $\begingroup$ Thanks. Your answer made me think in terms of induction. Firstly, this is the definition of induction I know and understand. Prove that the statement holds for a base case (generally 0, or 1). Then prove that for every x, if the statement holds for x then it holds for x + 1. Now, we will do an induction on (m,n,r,b) . Let us take the base case to be m = 2, n = 2 , r = 2, b = 2. It is obvious that in this case, the number of purples would be r * b = 4 . Having proven the base case, if we can prove the following 2 things also, then we can prove that (15 , 15, 5 , 5 ) is true. $\endgroup$ – Hemant Agarwal Apr 9 at 3:55
  • $\begingroup$ These are those 2 things : If it is true for (a,b,c,d) then it is true for (a, b+1, c+1, d) and, if it is true for (a, b, c, d) then it is also true for ( a+1, b, c, d+1). Now, in the ans given on the original link, instead of trying to prove for a general (a, b, c, d) , the author just proves it for the particular cases : (a, b, c, d) = (15, 14, 4, 5) and for (a, b, c, d) = (14, 15, 5, 4). He gives these example so that they can be extended to prove the general case. Am I right ? Also, why are we calling it m+n+r+b and not (m,n,r, b) ? What is the purpose of adding these terms up ? $\endgroup$ – Hemant Agarwal Apr 9 at 3:56
  • 1
    $\begingroup$ The author does prove it in general. When you expressed doubt, he gave in comments an illustrative example for the case (15,15,5,5). That involves reducing it to the case (15,4,5,4) or (14,15,4,5), which if the case you're looking at is (15,15,5,5) you can (by induction) safely assume is already known to work. $\endgroup$ – Gareth McCaughan Apr 9 at 13:19

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.