CTK Insights

26 Apr

Not too easy - not too difficult

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 n be an odd positive integer, and let x_1,x_2,\ldots,x_n be non-negative real numbers. Prove that


where x_{n+1}=x_1.

At first sight, the inequality appeared strange, if not erroneous because, for every two positive numbers a and b, a^2+b^2\ge 2ab since the latter reduces to (a-b)^2\ge 0.

Assuming, however, that the problem posed a meaningful question, it appears to be essential to take into account the fact that n was an odd number. This leads to the assumption that n\ge 3. The moment that the magnitude of n 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 a,b,c, listed in that order, and that a^2+b^2\le b^2+c^2 and a^2+b^2\le c^2+a^2. These imply a\le c and b\le c. Without loss of generality, a\le b\le c. Then, obviously, bc is the maximum of the three products. We need to show that a^2+b^2\le 2bc. This follows from a^2+b^2\le 2b^2\le 2bc.

Now, the intuition for the inductive step: in passing from n to n+2 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 n to n+1 such that the requirement that n is odd may be a red herring, only stipulated as a disguised substitute for n\ge 3.

Well, trying to implement the induction I ran into one essential difficulty: increasing n not only leads to additional terms among which to choose maximum or minimum, it also causes the terms x_n^2+x_1^2 and 2x_nx_1 to be dropped from consideration. If neither \displaystyle x_n^2+x_1^2=\min_{1,2,\ldots,n}(x_{i}^{2}+x_{i+1}^{2}) nor \displaystyle2x_nx_1=\max_{1,2,\ldots,n}2x_ix_{i+1} 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, \displaystyle x_n^2+x_1^2=\min_{1,2,\ldots,n}(x_{i}^{2}+x_{i+1}^{2}) then, in particular x_n^2+x_1^2\le x_1^2+x_2^2, implying x_n\le x_2 and, subsequently, 2x_nx_1\le 2x_1x_2 so that the removal of 2x_nx_1 could not affect the maximum on the right. Similarly, if \displaystyle2x_nx_1=\max_{1,2,\ldots,n}2x_ix_{i+1} then x_n\ge x_2 from which x_n^2+x_1^2\ge x_1^2+x_2^2 and so the removal of x_n^2+x_1^2 would have no effect on \displaystyle \min_{1,2,\ldots,n}(x_{i}^{2}+x_{i+1}^{2}).

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 x_1,x_2,\ldots,x_n with 0 or 1. When x_i\le x_{i+1} I replaced x_i with 0; otherwise it became 1. (Of course x_{n} was followed by x_1.) Now I had a sequence of 0's and 1'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 0s or two consecutive 1s. 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 1 between two zeros is liable to cause damage to the sequence unless the two zeros were a part of a triple 000. If it was not, i.e., if we attempted to insert 1 between the two zeros in 1001, we'd get 10101.

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 1s or 0s. In other words, it's an intermittent sequence of 1s and 0s. 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 n even there are bad sequences: 010101\ldots 1 while, for n odd, all sequences are good, for, in a bad sequence every 0 may be paired with a preceding 1 which makes its length even. Thus the induction from n to n+1 did not have a chance to succeed. It also proved to be altogether unnecessary due to a simple statement:

For n odd, all sequences of 1s and 0s are good.

The required inequality holds for any sequence that reduces to a good one, i.e., for any sequence of odd length. Woof.

2 Responses to “Not too easy - not too difficult”

  1. 1
    Grégoire Nicollier Says:

    A geometric proof. n is for the moment any positive integer. Suppose that every product 2 x_i x_{i+1} is smaller than every sum x_j^2+x_{j+1}^2 and consider the points (x1,x2),(x2,x3),...,(xn,x1) of the first quadrant. No point lies thus on y=x and we suppose without loss of generality that x1^2+x2^2 is minimal and equal to 1. All points are then in the first quadrant, not on y=x, and between (or on) the unit circle and the hyperbola xy=1/2 (but not on the hyperbola). The points lie thus alternately on the left and on the right of y=x (beginning with the side of (x1,x2)): the number of points is even.
    Grégoire Nicollier

  2. 2
    admin Says:

    That is very nice. If you follow the link in the first paragraph you'll see that Mike Lawler tried to follow Timothy Gowers' example of showing one's reasoning in solving a problem. Mike issued a challenge to do that for the problem above. This is what I tried to do. Is it too much trouble for you to explain how you arrived at your solution. This could be a nice collection.

Leave a Reply

Time limit is exhausted. Please reload the CAPTCHA.

© 2018 CTK Insights | Entries (RSS) and Comments (RSS)

Powered by Wordpress, design by Web4 Sudoku, based on Pinkline by GPS Gazette