# CTK Insights

• ## Pages

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

$\displaystyle\qquad\min_{1,2,\ldots,n}(x_{i}^{2}+x_{i+1}^{2})\le\max_{1,2,\ldots,n}2x_ix_{i+1},$

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 $0$s or two consecutive $1$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 $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 $1$s or $0$s. In other words, it's an intermittent sequence of $1$s and $0$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 $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 $1$s and $0$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.

#### 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