The other day, while driving my HS senior son to school (he could have taken a bus, but, for one, his time is at a premium; also, the drive gives us an opportunity for a small chat), we talked about how words with different basic meanings may mean the same thing in certain contexts. As an example I mentioned the expressions "not too late" and "not too early" both of which may mean "just in time." This conversation came to mind when I tried to characterize Problem #1 from the European Girls’ Math Olympiad which Mike Lawler posted on his recent blog:
Let be an odd positive integer, and let be non-negative real numbers. Prove that
At first sight, the inequality appeared strange, if not erroneous because, for every two positive numbers and , since the latter reduces to
Assuming, however, that the problem posed a meaningful question, it appears to be essential to take into account the fact that was an odd number. This leads to the assumption that The moment that the magnitude of came into the picture, the mathematical induction seemed like the one venue to follow to crack the problem.
To start with, suppose there are three non-negative real numbers , listed in that order, and that and These imply and Without loss of generality, Then, obviously, is the maximum of the three products. We need to show that . This follows from .
Now, the intuition for the inductive step: in passing from to the maximum on the right may only grow, whereas the minimum on the left may only decrease. This is naturally also true in passing from to such that the requirement that is odd may be a red herring, only stipulated as a disguised substitute for
Well, trying to implement the induction I ran into one essential difficulty: increasing not only leads to additional terms among which to choose maximum or minimum, it also causes the terms and to be dropped from consideration. If neither nor the underlying intuition worked just fine but bad things do happen and there was a need to account for the exceptional cases. The bright spot was that the two conditions can't complicate the proof simultaneously. If, for example, then, in particular implying and, subsequently, so that the removal of could not affect the maximum on the right. Similarly, if then from which and so the removal of would have no effect on
Beyond this, I had to consider several cases of where the dropped terms were smaller or greater of the added ones. I sought to simplify the situation and make it more formal. To this end, I replaced each number in the sequence with or . When I replaced with ; otherwise it became . (Of course was followed by .) Now I had a sequence of 's and 's. From the base of my attempted induction it transpired that "good" sequences (i.e., the sequences that satisfied the required inequality) were reducing to sequences that contain at least two consecutive s or two consecutive s. The question became to insert one or two digits and to verify that, starting with a good sequence, the insertion would always lead to a "good" sequence.
This process made it obvious that my attempt at induction was misguided. Clearly, some insertions will work but others will not. For example, inserting between two zeros is liable to cause damage to the sequence unless the two zeros were a part of a triple . If it was not, i.e., if we attempted to insert between the two zeros in , we'd get .
So what now? That stumbling step still had a positive effect: it led to a realization of what is a "bad" sequence. A bad sequence is the one that has no consecutive s or s. In other words, it's an intermittent sequence of s and s. I should have thought of this sooner without losing that much time. The idea of a bad sequence has highlighted another of my missteps. The fact is that for even there are bad sequences: while, for odd, all sequences are good, for, in a bad sequence every may be paired with a preceding which makes its length even. Thus the induction from to did not have a chance to succeed. It also proved to be altogether unnecessary due to a simple statement:
For odd, all sequences of s and s are good.
The required inequality holds for any sequence that reduces to a good one, i.e., for any sequence of odd length. Woof.