Convex Functions and Jensen's Inequality (Tuklas Vol. 17, No. 5 - October 24, 2015)

CONVEX FUNCTIONS AND JENSEN'S INEQUALITY

J. L. W. V. Jensen had the following to say about the beauty of convex functions [4]:

It seems to me that the notion of convex functions is just as fundamental as positive function[s] or increasing function[s]. If [I] am not mistaken in this, the notion ought to find its place in elementary expositions of the theory of real functions.

Convex functions play numerous roles in different fields in pure and applied mathematics, most notably in geometry, real analysis, probability theory, and nonlinear optimization. The modern-day appreciation and depth of the theory of convex functions is heavily attributed to Jensen, known for his inequality on convex functions that has become a stable discussion in any material on the theory of convexity. Jensen's Inequality has since then taken on various forms---a discrete form, a form which uses integrals, and a form using probabilities, among others. In relation to Jensen's statement on convex function, Steele refers to convexity as the ``third pillar'' of mathematical inequalities, along with positivity and monotonicity. [5]

The aim of this article is to provide the reader with initial insights on the theory of convex functions and the intuition and applications of Jensen's Inequality. As we shall see later, convex functions and Jensen's Inequality has earned a special spot as an indispensable technique in dissecting Olympiad-level inequalities. One of the most fundamental results related to Jensen's Inequality is that it can lead to what is called the generalized Arithmetic Mean-Geometric Mean Inequality. For a more detailed discussion of convex functions, the reader is encouraged to look at the references used for this article.

Before convex functions are introduced, we must first define what a convex set is. A set $S$ is a convex set if the line segment connecting any two points in $S$ is contained entirely in $S$. Mathematically, the set $S$ is convex if for any $x,y\in S$ and for any $\theta\in[0,1]$, the number $\theta x+(1-\theta)y$, called the convex combination of $x$ and $y$, is a member of the set $S$.

Figure 1: The two-dimensional sets above are examples of convex and non-
convex sets. The leftmost figure is a convex set, while the center and right-
most figures are not.

Convex functions, on the other hand, are functions defined on a convex set. A function $f$ is said to be convex on the interval $[a,b]$ if for any $x,y\in[a,b]$ (with $x<y$) and $\theta\in[0,1]$, $$f(\theta x+(1-\theta)y)\leq \theta f(x)+(1-\theta)f(y).$$ Graphically, this definition means that if we take any two points $A$ and $B$ on the graph of a convex function $f$, the line segment $AB$ should be above the graph $y=f(x)$. This characterization also means that the graph of convex functions are U-shaped or bowl-shaped on the interval $[a,b]$. Speaking in the language of averages, for a convex function, the function value of the weighted average of $x$ and $y$ is less than or equal to the weighted average of the function values at $x$ and $y$.

Figure 2: The graph of a convex function.

Calculus is also used to determine whether a function is convex. A function is convex on an interval $[a,b]$ if all tangent lines to the graph $y=f(x)$ on the interval lie below the graph of the function. Furthermore, a function is convex if its second derivative is nonnegative for all $x\in[a,b]$.

Examples of convex functions include the exponential function $f(x) = e^{ax}$ for any $a\in\mathbb{R}$, powers of absolute values $f(x) = |x|^p$ for $p\geq 1$, and the maximum function $f(x) =\max\{x_1,x_2,\dots,x_n\}$ for real numbers $x_1,x_2,\dots,x_n$.

There is a very nice quality of convex functions that makes this entire class of functions an attraction in the field of optimization. Notice that if a function $f$ is convex on an interval $[a,b]$, then its minimum value on $[a,b]$ is unique. A convex function also attains its maximum value at the endpoints of the interval considered; that is, if $f$ is convex on $[a,b]$, then the maximum value of $f$ is either $f(a)$ or $f(b)$. Furthermore, any local minimum is a global one; a strictly convex function (where the inequality is strictly less than) admits at most one minimum. In usual optimization, one may be looking at several local minima, but with (strictly) convex functions, we are guaranteed that there is only one minimum.

The most important result related to convex functions is Jensen's Inequality. This inequality states that if the real-valued function $f:[a,b]\to\mathbb{R}$ is convex, $x_1,x_2,\dots,x_n$ are numbers from an interval $[a,b]$, and $p_1,p_2,\dots,p_n$ are numbers in $[0,1]$ whose sum is $1$ (i.e. $\sum_{i=1}^n p_i = 1$), then it holds that $$f(p_1 x_1 + p_2 x_2 +\dots+p_n x_n) \leq p_1 f(x_1)+p_2 f(x_2)+\dots+p_n f(x_n).$$ Speaking in terms of weighted averages, Jensen's Inequality means that the function evaluated at the weighted average of the $x_i$'s is less than or equal to the weighted average of the functional values at the $x_i$'s. Notice also that if $n=2$, then the inequality reduces to the definition of convexity introduced earlier. Equality is attained when $x_1=x_2=\dots=x_n$.

The power of convex functions and Jensen's Inequality lies in the problem-solver's ability to spot a convex function in the given problem. Once the appropriate convex function has been identified, then the results above may be used to complete the solution to the problem. This step, however, is sometimes the most difficult when attempting to resolve an inequality problem.

To demonstrate the power of convex functions and Jensen's Inequality, we shall prove the generalized Arithmetic Mean-Geometric Mean (AM-GM) Inequality $$y_1^{p_1}\times y_2^{p_2}\times\dots\times y_n^{p_n} \leq p_i y_1 + p_2 y_2 + \dots + p_n y_n,$$ where the $y_i$'s are nonnegative numbers and the $p_i$'s are numbers in the interval $[0,1]$ that sum up to 1.

It turns out that one only has to resort to the exponential function $f(x)=e^x$, which we note is a convex function on the entire real number line. (We can verify its convexity based on its graph or using the defintion for convexity). Thus, for any $x_1,x_2,\dots,x_n\in\mathbb{R}$ and $p_i$'s satisfying the condition above, it holds that $$e^{p_1 x_1+p_2 x_2+\dots +p_n x_n} \leq p_1 e^{x_1}+p_2 e^{x_2}+\dots+p_n e^{x_n}.$$ Using the laws of exponents, we may rewrite the above equation as $$\left(e^{x_1}\right)^{p_1}\times\left(e^{x_2}\right)^{p_2}\times\dots\times \left(e^{x_n}\right)^{p_n} \leq p_1 e^{x_1}+p_2 e^{x_2}+\dots+p_n e^{x_n}.$$ Let $y_i = e^{x_i}$ for all $i=1,2,\dots,n$. Then the previous equation can be written as $$y_1^{p_1}\times y_2^{p_2}\times\dots\times y_n^{p_n} \leq p_1 y_1 + p_2 y_2 +\dots+p_n y_n.$$ Thus, the generalized AM-GM Inequality has been proven.

Another problem in which convexity and Jensen's Inequality can be used is the following [5]:

In an equilateral triangle with area $A$, the product of any two sides is equal to $4A/\sqrt{3}$. Show that there exist two sides whose lengths have a product that is greater than or equal to $4A/\sqrt{A}$.

To solve this, one may find useful some formulas that give the area of a triangle given side lengths and measures of interior angles. In particular, we note that if $a$, $b$, and $c$ are side lengths of a triangle and $\alpha$, $\beta$, and $\gamma$ are the angles opposite $a$, $b$, and $c$, respectively, then $$A = \frac{1}{2}ab\sin\gamma = \frac{1}{2}ac\sin\beta = \frac{1}{2}bc\sin\alpha.$$ The rest of the solution is left to the reader; as before, to use Jensen's Inequality, we must first be able to identify a convex function from the given problem. What do you think is the convex function we can use?

In the theory of inequalities, there are three pillars---positivity, monotonicity, and convexity. As we have shown in the foregoing exposition, convex functions significantly recur in the study of various mathematical relationships between numbers and functions. Its far-reaching beauty, with the aid of Jensen's Inequality, will continue to grace various applications in the optimization of functions and other fields involving a mastery of mathematical inequalities.

ABOUT THE AUTHOR:
Len Patrick Garces is an Instructor at the Ateneo de Manila University. He obtained his Master of Applied Mathematics major in Mathematical Finance degree at the Ateneo de Manila University in 2015.

REFERENCES:

[1] Boyd, S. & L. Vanderberghe. (2009). Convex Optimization. Cambridge University Press.
[2] Bautista, E. P & I. J. L. Garces. (2010). Mathematical Excursions: A Problem-Solving Primer for Trainers and Olympiad Enthusiasts. C&E Publishing, Inc.
[3] Manfrino, R. B, J. A. G. Ortega & R. V. Delgado. (2005). Inequalities: A Mathematical Olympiad Approach. Birkhauser.
[4] Niculescu, C. P. & L. E. Persson. (2004). Convex Functions and their Applications: A Contemporary Approach. Springer.
[5] Steele, J. M. (2004). The Cauchy-Schwarz Master Class: An Introduction to the Art of Mathematical Inequalities. Cambridge University Press.

OLYMPIAD CORNER

Team Selection Test for the 55th IMO, Bulgaria

Problem:  Find the least positive real number $\alpha$ with the following property: if the weight of a finite number of pumpkins is $1$ ton and the weight of every pumpkin is not more than $\alpha$ tons then the pumpkins can be distributed in 50 boxes (some of the boxes may remain empty) such that there are no more than $\alpha$ tons of pumpkins in every box.

Solution: 

Claim: the real number $\alpha$ that satisfies the above conditions is $\alpha =\frac{2}{51}.$

Suppose that $\alpha <\frac{2}{51}$, and let $k\geq 0$ be a nonnegative integer such that $$\frac{1}{51\times 2^{k}}\leq \alpha <\frac{1}{51\times 2^{k-1}}$$ Consider $51\times 2^{k}$ pumpkins, each having a weight of $\frac{1}{51\times 2^{k}}$ tons. Since there are 50 boxes, and $50<51\times 2^{k}$ for any nonnegative integer $k$, then by the pigeonhole principle, there exists a box with at least two pumpkins, with combined weight of at least $\frac{1}{51\times 2^{k-1}}>\alpha$. This is a contradiction.

We now show that $\alpha =\frac{2}{51}$. Suppose that we have a total of $m$ pumpkins, and we place a pumpkin in each of the $m$ empty boxes. Take two of the lightest boxes; if the combined weight is at most $\frac{2}{51}$, we transfer all the pumpkins into one of these boxes and remove the other. When the operation terminates, let $n$ be the number of boxes remaining. Suppose $x_{1}\leq x_{2}\leq \cdots \leq x_{n}$ represent the weights (in tons) of pumpkins in the $n$ boxes. Note that based on the procedure, $x_{i}\leq \frac{2}{51}$ for all $i=1,2,...,n$, which means we have distributed $m$ pumpkins into $n$ boxes such that there is no more than $\frac{2}{51}$ tons of pumpkins in every box. Moreover, since $x_{1}+x_{2}>\frac{2}{51}$ and $x_{1}\leq x_{2}$, then $x_{2}>\frac{1}{51}$. Therefore $$x_{1}+x_{2}+\cdots +x_{n}>\frac{2}{51}+\left( n-2\right) \frac{1}{51}$$ But since the sum of weights is $1$, then $$\frac{2}{51}+\left( n-2\right) \frac{1}{51}< 1\Rightarrow n<51$$ Hence we have distributed the pumpinks in no more than $50$ boxes such that weight in each box does not exceed $\frac{2}{51}$.

SOLUTIONS

(for October 10, 2015)

13. Determine the values of $x$ such that $2^{x}+3^{x}-4^{x}+6^{x}-9^{x}\leq1$. (Taken from 101 Problems in Algebra by Andreescu and Feng)
    (Solved by Jarrett Ian G. Lim [Philippine Academy of Sakya] and Farrell Eldrian Wu [MGC New Life Christian Academy]; partial credit for Joyce Heidi Ong [Chiang Kai Shek College], Steven Reyes [Saint Jude Catholic School], and Madeline Tee [Jubilee Christian Academy])
    
    
    SOLUTION: 
    Note that, for any value of $x$, $$\begin{align*} -2^{x}-3^{x}+4^{x}-6^{x}+9^{x}+1 & = \frac{1}{2}\left[\left(4^{x}-2\cdot6^{x}+9^{x}\right)+\left(4^{x}-2\cdot2^{x}+1\right)\right.\\ &\quad \left.+\left(9^{x}-2\cdot3^{x}+1\right)\right]\\ & = \frac{1}{2}\left[\left(2^{x}-3^{x}\right)^{2}+\left(2^{x}-1\right)^{2}+\left(3^{x}-1\right)^{2}\right]\\ & \geq 0, \end{align*}$$ because we just have a sum of squares of real numbers. This means that $$\begin{align*} -2^{x}-3^{x}+4^{x}-6^{x}+9^{x}+1 & \geq 0\\ 1 & \geq 2^{x}+3^{x}-4^{x}+6^{x}-9^{x} \end{align*}$$ for all $x$. Therefore, the solution set is $\mathbb{R}$.
14. Let $n$, $a$, and $b$ be positive integers. Prove that $$\gcd\left(n^{a}-1,n^{b}-1\right)=n^{\gcd\left(a,b\right)}-1.$$ (First Stage, Moscow Mathematical Olympiad, 1995)
    (Solved by Jarrett Ian G. Lim [Philippine Academy of Sakya], Joyce Heidi Ong [Chiang Kai Shek College], and Farrell Eldrian Wu [MGC New Life Christian Academy]; partial credit for Madeline Tee [Jubilee Christian Academy])
    
    
    SOLUTION: 
    What we will show is that the expression on the left will divide the expression on the right, and vice-versa.
    
    First note that $\gcd\left(a,b\right)$ must divide both $a$ and $b$. Also, for any expression $n^{x}-1$, if $y|x$, then $$n^{x}-1=\left(n^{y}-1\right)\left(n^{x-y}+n^{x-2y}+\cdots+1\right).$$ Since $\gcd\left(a,b\right)$ divides $a$ and $b$, then $n^{\gcd\left(a,b\right)}-1$ must also divide both $n^{a}-1$ and $n^{b}-1$, that is, $n^{\gcd\left(a,b\right)}-1$ is a common factor of $n^{a}-1$ and $n^{b}-1$. Consequently, $n^{\gcd\left(a,b\right)}-1$ must divide $\gcd\left(n^{a}-1,n^{b}-1\right)$.
    
    We now work with the second part, which is to prove that $\gcd\left(n^{a}-1,n^{b}-1\right)$ divides $n^{\gcd\left(a,b\right)}-1$. Recall that if $\gcd\left(a,b\right)$ denotes the greatest common divisor of $a$ and $b$, then there exists $x$, $y$ such that $ax-by=\gcd\left(a,b\right)$. Specifically, we can choose $x$ and $y$ to be positive. Now, following a similar argument as in the first part, we now know that $n^{a}-1$ will divide $n^{ax}-1$ and $n^{b}-1$ will divide $n^{by}-1$.
    
    This means that $\gcd\left(n^{a}-1,n^{b}-1\right)$ divides $n^{ax}-1$ and $n^{by}-1$. So $\gcd\left(n^{a}-1,n^{b}-1\right)$ divides $\left(n^{ax}-1\right)-\left(n^{by}-1\right)$.
    
    Note that $$\begin{align*} \left(n^{ax}-1\right)-\left(n^{by}-1\right) & = n^{by}\left(n^{ax-by}-1\right)\\ & = n^{by}\left(n^{\gcd\left(a,b\right)}-1\right). \end{align*}$$ Again, $\gcd\left(n^{a}-1,n^{b}-1\right)$ divides $\left(n^{ax}-1\right)-\left(n^{by}-1\right)$, and since $n^{a}-1$ and $n^{b}-1$ are both $-1\left(\mod n\right)$ while $n^{by}\equiv0\left(\mod n\right)$, we have $\gcd\left(n^{by},\gcd\left(n^{a}-1,n^{b}-1\right)\right)=1$. This means that $\gcd\left(n^{a}-1,n^{b}-1\right)$ divides $n^{\gcd\left(a,b\right)}-1$.
15. Let $a$ and $b$, with $a\geq b$ be roots of $x^{2}-3x-50=0$. Determine the value of $a^{3}-2014b^{2}+2015$.
    (Solved by Jarrett Ian G. Lim [Philippine Academy of Sakya], Joyce Heidi Ong [Chiang Kai Shek College], and Farrell Eldrian Wu [MGC New Life Christian Academy]; partial credit for Madeline Tee [Jubilee Christian Academy])
    
    
    SOLUTION: 
    This item has two solutions.
    
    The first is the more tedious one, where we actually get the values of $a$ and $b$ via the quadratic formula, and substitute them into the expression $a^{3}-2014b^{2}+2015$, but this is tedious.
    
    The second involves a more intricate approach. First, note that by Vieta's Theorem, we have $a+b=3$ and $ab=-50.$
    
    Let $$A=a^{3}-2014b^{2}+2015$$ and $$B=b^{3}-2014a^{2}+2015.$$ Adding $A$ and $B$, we get $$A+B=\left(a^{3}+b^{3}\right)-2014\left(a^{2}+b^{2}\right)+2030$$ The first expression can be factored as $$\begin{align*} A+B & = \left(a+b\right)\left(a^{2}-ab+b^{2}\right)-2014\left(a^{2}+b^{2}\right)+2030\\ & = \left(a+b\right)\left(a^{2}+2ab+b^{2}-3ab\right)-2014\left(a^{2}+2ab+b^{2}-2ab\right)+2030\\ & = \left(a+b\right)\left[\left(a+b\right)^{2}-3ab\right]-2014\left[\left(a+b\right)^{2}-2ab\right]+2030\\ & = 3\left[3^{2}+150\right]-2014\left(3^{2}+100\right)+2030\\ & = -217,109. \end{align*}$$ Similarly, $$\begin{align*} A-B & = \left(a^{3}-b^{3}\right)+2014\left(a^{2}-b^{2}\right)\\ & = \left(a-b\right)\left[\left(a+b\right)^{2}-ab+2014\left(a+b\right)\right]. \end{align*}$$ Now, where will we get the values of those expressions? We go back to the original equation which reads $x^{2}-3x-50=0$.
    
    It can be shown that the sum of the roots is 3, and the product of the roots is $-50$. Since $a\geq b$, then $a-b$ is nonnegative, so $$\begin{align*} a-b & = +\sqrt{\left(a-b\right)^{2}}\\ & = \sqrt{\left(a+b\right)^{2}-4ab} \end{align*}$$ This means that $$\begin{align*} a+b & = 3\\ ab & = -50\\ a-b & = \sqrt{209}. \end{align*}$$ This means that $$\begin{align*} A-B & = \sqrt{209}\left[9+50+2014\left(3\right)\right]\\ & = 6101\sqrt{209}. \end{align*}$$ Solving for $A$ from $A+B=-217,109$ and $A-B=6,101\sqrt{209}$, we get $$A=\frac{6,101\sqrt{209}-217,109}{2}.$$
16. Four spheres have radii $2$, $2$, $3$, and $3$ respectively. Each sphere is tangent to three others. There is another sphere which is tangent to all these four spheres. Determine the radius of this sphere. (China, 1995)
    (Solved by Jarrett Ian G. Lim [Philippine Academy of Sakya] and Farrell Eldrian Wu [MGC New Life Christian Academy]; partial credit for Madeline L. Tee [Jubilee Christian Academy])
    
    
    SOLUTION: 
    Let $A$ and $B$ be the centers of the two spheres of radius $2$, and $C$ and $D$ the centers of the two spheres of radius $3$. Let $E$ and $r$ be the center and radius of the sphere tangent to all others.
    
    In addition, let $M$ and $N$ be the midpoints of $AB$ and $CD$, respectively.
    
    First, note that $AC=AD=5$, and $N$ is the midpoint of $CD$. This means that $AN$ is perpendicular to $CD$. So we can use Pythagorean Theorem on $\triangle ANC$ to show that $$\begin{align*} AC^{2} & = AN^{2}+NC^{2}\\ 5^{2} & = AN^{2}+3^{2}\\ AN & = 4. \end{align*}$$ Now, $MN$ is perpendicular to $AB$, so we can again use Pythagorean Theorem on $\triangle AMN$ and see that $$\begin{align*} AN^{2} & = AM^{2}+MN^{2}\\ 4^{2} & = 2^{2}+MN^{2}\\ MN & = \sqrt{12}. \end{align*}$$ Now we focus our attention to the sphere with center $E$. It must be noted that, for the sphere with center at $E$ to be tangent to all four spheres, $E$ must lie on the perpendicular bisecting planes of both $AB$ and $CD$, which intersect at the line in which $MN$ is a segment of. This means that $E$ lies on segment $MN$.
    
    Moreover, $\triangle EMA$ is a right triangle with $AM=2$ and $AE=r+2$. We now have $$\begin{align*} AE^{2} & = AM^{2}+ME^{2}\\ \left(r+2\right)^{2} & = 2^{2}+ME^{2}\\ ME & = \sqrt{r^{2}+4r}. \end{align*}$$ Similarly, working with $EN$, we will get $EN=\sqrt{r^{2}+6r}$. Since $E$ lies on segment $MN$, we have $$\begin{align*} MN & = ME+EN\\ \sqrt{12} & = \sqrt{r^{2}+4r}+\sqrt{r^{2}+6r}\\ \left(\sqrt{12}-\sqrt{r^{2}+6r}\right)^{2} & = \left(\sqrt{r^{2}+4r}\right)^{2}\\ 12-2\sqrt{12r^{2}+72r}+r^{2}+6r & = r^{2}+4r\\ 2r+12 & = 2\sqrt{12r^{2}+72r}\\ \left(r+6\right)^{2} & = \left(\sqrt{12r^{2}+72r}\right)^{2}\\ r^{2}+12r+36 & = 12r^{2}+72r\\ 0 & = 11r^{2}+60r-36\\ r & = \frac{6}{11},-6. \end{align*}$$ This means that the radius of the sphere tangent to all others is $\dfrac{6}{11}$.
17. Let $P_{1}P_{2}\dots P_{12}$ be a regular dodecagon. Prove that $P_{1}P_{5}$, $P_{4}P_{8}$, and $P_{3}P_{6}$ are concurrent (they intersect at the same point). (23rd Putnam, 1963)
    (Partial credit for Jarrett Ian G. Lim [Philippine Academy of Sakya], Joyce Heidi Ong [Chiang Kai Shek College], Madeline Tee [Jubilee Christian Academy], Farrell Eldrian Wu [MGC New Life Christian Academy])
    
    
    SOLUTION: 
    Consider the added points $Q_{1},Q_{2},\dots,Q_{6}$ such that $Q_{1}Q_{2}\dots Q_{6}$ is a regular hexagon of the same length as the original dodecagon. This can be done by forming equilateral triangles $P_{1}P_{2}Q_{1}$, $P_{3}P_{4}Q_{2}$, and so on until $P_{11}P_{12}Q_{6}$.
    
    

    

    
    
    Since the measure of one interior angle of a dodecagon is $150^{\circ}$, then we can say that $\angle P_{3}P_{2}Q_{1}=\angle P_{5}P_{4}Q_{2}=\cdots=\angle P_{1}P_{12}Q_{6}=90^{\circ}$. As a consequence, we have formed six squares in the process.
    
    We first focus our attention to the isosceles triangle $P_{1}Q_{1}Q_{2}$. Here, note that the vertex angle is $\angle P_{1}Q_{1}Q_{2}$, which measures $150^{\circ}$. This means that $\angle Q_{1}Q_{2}P_{1}=\angle Q_{1}P_{1}Q_{2}=15^{\circ}$.
    
    Since $Q_{2}P_{5}$ is the diagonal of square $P_{4}P_{5}Q_{3}Q_{2}$, we have $\angle P_{5}Q_{2}Q_{3}=45^{\circ}$. Of course we also have $\angle Q_{1}Q_{2}Q_{3}=120^{\circ}$.
    
    This means that $$\angle P_{1}P_{2}Q_{1}+\angle Q_{1}Q_{2}Q_{3}+\angle P_{5}Q_{2}Q_{3}=180^{\circ},$$ which means that $P_{1}Q_{2}P_{5}$ form a line segment. Similarly, we can say that $P_{4}Q_{3}P_{8}$ form a line segment as well.
    
    Consequently, $P_{1}P_{5}$ and $P_{4}P_{8}$ intersect at the center of square $P_{4}P_{5}Q_{3}Q_{2}$.
    
    By our construction, $\triangle P_{3}P_{4}Q_{2}$ and $\triangle P_{5}Q_{3}P_{6}$ are symmetric with respect to the center of square $P_{4}P_{5}Q_{3}Q_{2}$. As such, $P_{3}P_{6}$ serves as the perpendicular bisector of $P_{4}Q_{2}$ and $P_{5}Q_{3}$. This means that indeed, $P_{3}P_{6}$ must pass through the center of square $P_{4}P_{5}Q_{3}Q_{2}$ as well.
    
    So $P_{1}P_{5}$, $P_{4}P_{8}$, and $P_{3}P_{6}$ intersect at the same point.
18. For each permutation $a_{1},a_{2},\dots,a_{2014}$ of the integers $1, 2, \dots, 2014$, form the sum $$\sum_{i=1}^{1007}\left|a_{2i-1}-a_{2i}\right|.$$ Find the average value of all these sums. (American Invitational Mathematics Examination, 1996)
    (Solved by Jarrett Ian G. Lim [Philippine Academy of Sakya] and Farrell Eldrian Wu [MGC New Life Christian Academy]; partial credit for Madeline Tee [Jubilee Christian Academy])
    
    
    SOLUTION: 
    We first focus on the average value of $A=\left|a_{1}-a_{2}\right|$. Since we are just taking permutations, then we can just take the average value of $A$, because this average value will be the same for all $\left|a_{2i-1}-a_{2i}\right|$, so the average that we want is just $1007$ times the average value of $A$.
    
    Now, if $a_{1}=x$, $x\in\left\{ 1,2,\dots,2014\right\}$, then the average value of $A$ is just $$\begin{align*} \frac{\left(x-1\right)+\left(x-2\right)+\cdots+1+1+2+\cdots+\left(2014-x\right)}{2013} & = \frac{1}{2013}\left[\frac{x\left(x-1\right)}{2}+\frac{\left(2014-x\right)\left(2015-x\right)}{2}\right]\\ & = \frac{x^{2}-2015x+1007\left(2015\right)}{2013}. \end{align*}$$ Now we need to take the sum of all possible average values when we vary the value of $a_{1}$. This means that we have $$\begin{align*} \frac{1}{2014}\sum_{x=1}^{2014}\frac{x^{2}-2015x+1007\left(2015\right)}{2013} & = \frac{1}{2014}\frac{1}{2013}\\ & \quad \cdot\left[\frac{2014\left(2015\right)\left(2031\right)}{6}-\frac{2015\left(2014\right)\left(2015\right)}{2}\right.\\ & \quad \left.+1007\left(2014\right)\left(2015\right)\right]\\ & = \frac{1}{2014}\frac{1}{2013}\\ & \quad \cdot\left[\frac{2014\left(2015\right)\left(2029\right)}{6}-\frac{3\cdot2015\left(2014\right)\left(2015\right)}{6}\right.\\ & \quad \left.+\frac{3\cdot2014\left(2014\right)\left(2015\right)}{6}\right]\\ & = \frac{2015}{3}. \end{align*}$$ This means that the average value of all possible sums is just $\dfrac{\left(1007\right)\left(2015\right)}{3}.$