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}.$

Sigma Graph Coloring (Tuklas Vol. 17, No. 4 - October 10, 2015)

SIGMA GRAPH COLORING

Figure 1: Graph $G$ with 3 vertices and 3 edges

Consider the figure above. This object is called a graph, and it can be used to represent a wide variety of things. For instance, it can be used to represent a road network or a map of social relationships. A graph consists of a set of points called vertices, where some pairs of vertices are joined by a line called an edge. We say that the two vertices $v_1$ and $v_2$ are adjacent if there is an edge $e$ that connects $v_1$ and $v_2$.

For any vertex $v$ in $G$, the neighbor of $v$ is the vertex adjacent to $v$. Looking back at the previous illustration, the vertex $v_1$ in $G$ has neighbors $v_2$ and $v_3$.

Mathematicians like to play around with graphs, because the properties that can be derived are very interesting. For instance, a vertex coloring of a graph $G$ refers to an assignment of colors to the vertices in $G$. We use positive integers $1,2, \ldots , n$ as colors to be assigned to the vertices in a graph. Why does it have to be positive integers? It is because we are interested in the number of colors to be used. A color sum of a vertex $v$ is the sum of the colors of the neighbors of $v$. We write the color sum of $v$ as $\sigma$ (sigma).

Moreover, a vertex coloring is a sigma coloring if for any two neighboring vertices, their color sums are not equal. In fact, a graph $G$ has sigma $k$-coloring if we can assign at most $k$ colors to the vertices in $G$.

In the figure below, consider a graph with a sigma $3$-coloring. We choose the colors $2$, $5$, and $9$ to label the vertices in $G$.

Figure 2: Sigma 3-coloring of $G$

Indeed, as shown above, any two neighboring vertices in $G$ have distinct color sums. Therefore, $G$ has sigma $3$-coloring.

Notice that the following figure shows sigma colorings of the graph $H$ with $6$ vertices and $6$ edges.

Figure 3: Examples of sigma colorings

We note that any graph with $n$ vertices has a sigma $k$-coloring where, $1 \leq k \leq n$. However, what if we want to determine the smallest number of colors needed in a sigma coloring of a graph? In other words, we want to find the smallest value of $k$ in which a sigma $k$-coloring exists. The minimum value of $k$ is called the sigma chromatic number of a graph. Now, we recall the graph $H$ above. Suppose we assign all the vertices in $H$ with only one color, say, $7$.

Figure 4: Not a sigma coloring of $H$

The illustration above shows that $H$ has no sigma $1$-coloring because any two neighboring vertices have equal color sum. Since $H$ is sigma $2$-colorable (as shown in (d) above), the sigma chromatic number of $H$ is $2$.

Mathematicians have been fascinated by sigma graph coloring not just because of the math involved, but also because of the real life applications. Some of these involve club scheduling problems and hospital planning. Can you think of an application of sigma graph coloring in daily life?

ABOUT THE AUTHOR:
Maria Czarina T. Lagura is a graduate assistant at the Ateneo de Manila University. She is currently taking her Master's degree at the same university.

REFERENCES:

- Chartrand, G. and P. Zhang. Chromatic Graph Theory, Chapman & Hall/CRC Press, Boca Raton, FL (2009).
- Chartrand, G., F. Okamoto, P. Zhang. "The Sigma Chromatic Number of a Graph." Graph and Combinatorics, 26:755-773 (2010).

OLYMPIAD CORNER

from the 51st International Mathematical Olympiad, 2010 (Shortlist)

Problem:  Given six positive numbers $a$, $b$, $c$, $d$, $e$, $f$ such that $a < b < c < d < e < f$. Let $a + c + e = S$ and $b + d + f = T$. Prove that $$2ST > \sqrt{3\left( S+T\right) \left( S\left(bd+bf+df\right) +T\left(ac+ae+ce\right) \right) }$$

Solution: 

Let $\alpha =ac+ce+ae$ and $\beta =bd+bf+df$. Moreover, let $s=c+e$, hence $a=S-s$.

Note that $$\left( c-b\right) \left( c-d\right) +\left( e-f\right) \left( e-d\right) +\left( e-f\right) \left( c-b\right) < 0,$$ since each summand is negative. We can rewrite this as $$\begin{align} \left( bd+bf+df\right) -\left( ac+ce+ae\right) &< \left( c+e\right) \left( b+d+f-a-c-e\right) \\ \beta -\alpha &< s\left( T-S\right) \end{align}$$ and we have $$S\beta +T\alpha =S\left( \beta -\alpha \right) +\left( S+T\right) \alpha < Ss\left( T-S\right) +\left( S+T\right) \left( ce+as\right)$$ Since $\left( c-e\right) ^{2}\geq 0$, then $\frac{(c+e)^{2}}{4}\geq ce$.

Hence, $$S\beta +T\alpha < Ss\left( T-S\right) +\left( S+T\right) \left( \frac{s^{2}}{4}+\left( S-s\right) s\right) =s\left( 2ST-\frac{3}{4}\left( S+T\right) s\right)$$ Using the AM-GM Inequality, we have $$\begin{align} \sqrt{\frac{3}{4}\left( S+T\right) \left( S\beta +T\alpha \right) } & < \sqrt{\frac{3}{4}\left( S+T\right) s\left( 2ST-\frac{3}{4}\left( S+T\right) s\right) } \\ &\leq \frac{\frac{3}{4}\left( S+T\right) s+2ST-\frac{3}{4}\left( S+T\right) s}{2}=ST \end{align}$$ Therefore $$2ST > \sqrt{3\left( S+T\right) \left( S\left( bd+bf+df\right) +T\left( ac+ae+ce\right)\right)}.$$

PROBLEMS

13. Determine the values of $x$ such that $2^{x}+3^{x}-4^{x}+6^{x}-9^{x}\leq1$.
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.$$
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$.
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.
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).
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.

We welcome readers to submit solutions to the problems posed below for publication consideration. Solutions may ONLY be submitted online via vantonio1992@gmail.com. Solutions must be preceded by the solver's name, school affiliation and year level. The deadline for submission is 12:30 PM October 24, 2015.

SOLUTIONS

(for October 3, 2015)

10. Find all values of $x$, $y$, and $z$ such that $x^4+y^4+z^4-4xyz=-1$.
    (Solved by Jarrett Ian G. Lim [Philippine Academy of Sakya], Joyce Heidi Ong [Chiang Kai Shek College], Ryan Jericho Sy [Chang Kai Shek College], Farrell Eldrian Wu [MGC New Life Christian Academy]; partial credit for Madeline L. Tee [Jubilee Christian Academy])
    
    
    SOLUTION: 
    We have $$\begin{align*} -1 & = x^{4}+y^{4}+z^{4}-4xyz\\ 0 & = x^{4}+y^{4}+z^{4}-4xyz+1\\ & = \left(x^{4}-2x^{2}y^{2}+y^{4}\right)+\left(z^{4}-2z^{2}+1\right)-4xyz+2x^{2}y^{2}+2z^{2}\\ & = \left(x^{4}-2x^{2}y^{2}+y^{4}\right)+\left(z^{4}-2z^{2}+1\right)+2\left(x^{2}y^{2}-2xyz+z^{2}\right)\\ 0 & = \left(x^{2}-y^{2}\right)^{2}+\left(z^{2}-1\right)^{2}+2\left(xy-z\right)^{2}. \end{align*}$$ We have a sum of squares that is equal to 0. This means that each of the terms must be equal to $0$. From the second term, we have $$z=\pm1,$$ while from the first and the third we get $x=\pm y$ and $xy=z$. This means that if $z=1$, we have the solutions $\left(\pm1,\pm1,1\right)$, while for $z=-1$, we have $\left(\pm1,\mp1,-1\right)$.
11. Find the number of ways to color $2015$ points on a circle with $3$ colors such that any two neighboring points have distinct colors.
    (Partial credit for Jarrett Ian G. Lim [Philippine Academy of Sakya], Joyce Heidi Ong [Chiang Kai Shek College], Farrell Eldrian Wu [MGC New Life Christian Academy])
    
    
    SOLUTION: 
    Let us solve the problem for a general number of points $n$. Define $a_{n}$ to be the number of possible colorings for $n$ points on the circle.
    
    Note that if $n=1$, then $a_1=3$.
    
    If $n=2$, then the first point will have three color options, while the other will have one less option. We have $3\cdot2=6$ possible colorings, and consequently, $a_{2}=6$.
    
    Now, if $n=3$, then the first point will have three options, its neighboring point (to the right) will have 2 options, while the remaining point will only have 1. This means that $a_{3}=3\cdot2\cdot1=6$.
    
    On the other hand, if we have $n+1$ points. Consider the neighbors of the last added point. We have one color used for the last point. We have two cases.
    
    Consider the case when the two neighbors of this last added point has the same color. If its two neighbors share the same color, then the last added point will have two color options.
    
    Moreover, since the two neighbors have the same color, then we can just consider it as a single point, which means that, along with the rest of the points, the $n$ points can be colored $a_{n-1}$ ways. This means, in this first case, we have $2a_{n-1}$ colorings.
    
    On the other hand, if the two neighbors have different colors, then, there will only be one option for the last added point. Moreover, the rest of the $n$ points can be colored $a_{n}$ ways.
    
    This means that we have the recurrence relation (RR) $$a_{n+1}=a_{n}+2a_{n-1},$$ where $a_1=2$ and $a_{2}=a_{3}=6$. The closed form of this RR is given by $$a_{n}=2^{n}+2\left(-1\right)^{n}.$$ If we check, we have $$\begin{align*} a_{n}+2a_{n-1} & = \left[2^{n}+2\left(-1\right)^{n}\right]+2\left[2^{n-1}+2\left(-1\right)^{n-1}\right]\\ & = 2^{n}+2\left(-1\right)^{n}+2^{n}-4\left(-1\right)^{n}\\ & = 2^{n+1}+2\left(-1\right)^{n+1}\\ & = a_{n+1}. \end{align*}$$ Finally, we just need to obtain $a_{2015}=2^{2015}-2$ colorings.
12. Determine the minimum value of $\dfrac{a+b+c}{b-a}$ given that for all $x$, $ax^2+bx+c\geq 0$ and $a < b$.
    (Partial credit for Joyce Heidi Ong [Chang Kai Shek College], Ryan Jericho Sy [Chang Kai Shek College], Farrell Eldrian Wu [MGC New Life Christian Academy])
    
    
    SOLUTION: 
    First, note that if $a=0$, then $ax^{2}+bx+c=bx+c$. Since $0=a<b$, then $b$ is positive, then $$\begin{align*} bx+c & \geq 0\\ x & \geq -\frac{c}{b}. \end{align*}$$ This means that the condition $ax^{2}+bx+c\geq0$ is only true when $x\geq-\dfrac{c}{b}$.
    
    This means that $a\neq0$.
    
    We now have $$\begin{align*} 0 & \leq ax^{2}+bx+c\\ & = a\left(x^{2}+\frac{b}{a}x+\frac{b^{2}}{4a^{2}}\right)+\frac{4ac-b^{2}}{4a}\\ & = a\left(x+\frac{b}{2a}\right)^{2}+\frac{4ac-b^{2}}{4a}. \end{align*}$$ If $a<0$, then we can solve for $x$ such that the inequality is true, and certainly, the solution set of this inequality will not be $\mathbb{R}$, in fact, the values will have to be in the interval $$\left[\frac{-b-\sqrt{b^{2}-4ac}}{2a},\frac{-b+\sqrt{b^{2}-4ac}}{2a}\right].$$ This means that $a>0$.
    
    Now, if we want this expression to to always be greater than $0$, then the right side of the expression must be nonnegative as well. We must have $4ac-b^{2}\geq0$. This means that $c\geq\dfrac{b^{2}}{4a}$.
    
    Since we are trying to minimize $\dfrac{a+b+c}{b-a}$, we can minimize $c$ first. So we just get$c=\dfrac{b^{2}}{4a}$. Now, $$\begin{align*} \frac{a+b+c}{b-a} & = \frac{a+b+\dfrac{b^{2}}{4a}}{b-a}\\ & = \frac{4a^{2}+4ab+b^{2}}{4a\left(b-a\right)}\\ & = \frac{\left(9a^{2}+6ab-6a^{2}\right)+\left(b^{2}-2ab+a^{2}\right)}{4a\left(b-a\right)}\\ & = \frac{9a^{2}+6a\left(b-a\right)+\left(b-a\right)^{2}}{4a\left(b-a\right)}\\ & = \frac{9a}{4\left(b-a\right)}+\frac{3}{2}+\frac{\left(b-a\right)}{4a}. \end{align*}$$ Note that $b-a$ and $a$ are both positive. By AM-GM, we have $$\begin{align*} \frac{9a}{4\left(b-a\right)}+\frac{\left(b-a\right)}{4a} & \geq 2\sqrt{\frac{9a}{4\left(b-a\right)}\frac{\left(b-a\right)}{4a}}\\ & = \frac{3}{2}. \end{align*}$$ This means that the minimum value of $\dfrac{a+b+c}{b-a}$ is $\dfrac{3}{2}+\dfrac{3}{2}=3$. This can be achieved when $a=1$ and $b=4$, and $c=4$. Note that in this case, we have $x^2+4x+4=\left(x+2\right)^2\geq0$, so the condition is still satisfied.

The Latin Square (Tuklas Vol. 17, No. 3 - October 3, 2015)

THE LATIN SQUARE

Try filling the table above with numbers from the set $\{1,2,3\}$ such that no row or column contains the same number. If you have played Sudoku, you might be familiar with solving puzzles like this. These square puzzles, called Latin squares, have been around for a long time, even predating the game of Sudoku.

What is a Latin square? A Latin square of order $n$ is an $n\times n$ array of $n$ symbols such that each symbol appears exactly once in each row and once in each column. If you were able to solve the above square, the result is a Latin square of order $3$. Here are some examples of Latin squares:

D	A	C	B
B	C	A	D
C	D	B	A
A	B	D	C

D

A

C

B

B

C

A

D

C

D

B

A

A

B

D

C

,   

1	2	3	4	5	6
2	1	4	3	6	5
3	5	1	6	2	4
4	6	2	5	3	1
5	4	6	2	1	3
6	3	5	1	4	2

1

2

3

4

5

6

2

1

4

3

6

5

3

5

1

6

2

4

4

6

2

5

3

1

5

4

6

2

1

3

6

3

5

1

4

2

Figure 1: Latin squares of order 4 and 6.

Why is it called a “Latin” square? Though Latin squares had already existed for centuries, it was Leonhard Euler who formally introduced and developed the concept in 1783 in his mathematical paper entitled "nouveau espece de carres magiques". He used Latin characters as symbols, hence the term Latin square. Of course nowadays, one can use any other symbol to form a Latin square and not just Latin characters.

One of the most interesting problems involving a Latin square is the search for its orthogonal mate. It was again Euler who developed the definition of orthogonal Latin squares. Two Latin squares are said to be orthogonal if when superimposed (joined together), the ordered pairs in the resulting array are all distinct. When two Latin squares are orthogonal to each other, we call them orthogonal mates. Figure 2 shows two orthogonal Latin squares and their join. Notice that the elements of their join are all distinct.

$A=$

1	2	3	4
2	1	4	3
3	4	1	2
4	3	2	1

1

2

3

4

2

1

4

3

3

4

1

2

4

3

2

1

, $B=$

1	2	3	4
4	3	2	1
2	1	4	3
3	4	1	2

1

2

3

4

4

3

2

1

2

1

4

3

3

4

1

2

 

$(A,B) =$

(1,1)	(2,2)	(3,3)	(4,4)
(2,4)	(1,3)	(4,2)	(3,1)
(3,2)	(4,1)	(1,4)	(2,3)
(4,3)	(3,4)	(2,1)	(1,2)

(1,1)

(2,2)

(3,3)

(4,4)

(2,4)

(1,3)

(4,2)

(3,1)

(3,2)

(4,1)

(1,4)

(2,3)

(4,3)

(3,4)

(2,1)

(1,2)

Figure 2: 2 orthogonal Latin squares, denoted by A and B, alongside their join.

A classic problem that involves orthogonal Latin squares is the problem posted by Euler involving 36 officers from six ranks and six regiments. He claimed that it was impossible to arrange six regiments, each with six ranks (a colonel, a lieutenant-colonel, a major, a captain, a lieutenant, and a sub-lieutenant) in a $6 \times 6$ array such that no row or column duplicates a rank or a regiment. Thus, a Latin square of order $6$ does not have an orthogonal mate. Notice also that a Latin square of order $2$ does not have an orthogonal mate either (see Figure 3).

A	B
B	A

A

B

B

A

,   

B	A
A	B

B

A

A

B

Figure 3: The two Latin squares of order 2.

With this, Euler conjectured that no orthogonal Latin squares of order $6$ exist, nor does one exist whenever $n \equiv 2 \mod 4$. This remained as a conjecture for more than 100 years until 1960 when Bose, Shrikhande and Parker disproved it.

A Latin square has so many important characteristics and it has many applications in science, engineering, statistics and most importantly, in mathematics. In abstract algebra, Cayley tables of quasigroups and the addition table of integers modulo $n$ form a Latin square. In statistics, the Latin square design is used to control (or eliminate) two sources of the variation in an experiment. In coding theory, a pair of orthogonal Latin squares is used to design new techniques for what we call error correcting codes. In games, Sudoku puzzles and magic square puzzles are just two of most famous games that is related to Latin squares.

There are still so many things to discover about Latin squares - from construction, existence of orthogonal mate, up to the discovery of new applications. For instance, if we define a transversal of a Latin square as a set of entries which includes exactly one entry from each row and column and one of each symbol, one may try to solve this conjecture: Every Latin square of odd order has a transversal. Enjoy!

ABOUT THE AUTHOR:
Pejie Santillan is a graduate assistant at the Ateneo de Manila University. He is currently taking his Master's degree at the same university.

REFERENCES:

- Colbourn, C. J. and J. H. Dinitz (eds). The CRC Handbook of Combinatorial Designs, CRC Press, Boca Raton (1996).
- Arshaduzzaman, Md. "Connections between Latin Squares and Geometries." IOSR Journal of Mathematics, Vol. 9, Issue 5 (Jan 2014). Retrieved from http://iosrjournals.org/iosr-jm/papers/Vol9-issue5/C0951419.pdf.
- Waheed, Ali Makki Sagheer Makarim. Error-Correcting Code using Latin Square, Abdul-Jabbar. College of Computer, University of Anbar.

OLYMPIAD CORNER

from the Italian Mathematical Olympiad, 2014

Problem:  Prove that there exists a positive integer that can be written as a sum of $2015$ distinct $2014$th powers of positive integers $x_{1} < x_{2} < \cdots < x_{2015}$ in at least two ways.

Solution: 

Let $N$ be a positive integer greater than or equal to $2015$. The total number of increasing sequences $x_{1} < x_{2} < \cdots < x_{2015}$ such that all the terms are less than or equal to $N$ is given by $\binom{N}{2015}$. For each of these sequences, we find the sum $x_{1}^{2014}+x_{2}^{2014}+\cdots+x_{2015}^{2014}$. Since $x_{i}^{2014}\leq N^{2014}$ for any $i=1,2,...,2015$, it follows that the sum will be at most $2015N^{2014}$. Therefore we have $\binom{N}{2015}$ sums, and each sum is less than or equal to $2015N^{2014}$.

We claim that $\binom{N}{2015} > 2015N^{2014}$ for some $N$. Note that $$\binom{N}{2015}=\frac{N\left( N-1\right) \left( N-2\right) \cdots \left(N-2014\right) }{2015!}$$ Also consider $$P\left( N\right) =\frac{N\left( N-1\right) \left( N-2\right) \cdots \left(N-2014\right) }{2015!}-2015N^{2014}$$ Since $P\left( N\right)$ is a $2015$th degree polynomial with a positive leading coefficient, its graph will just conitinue to move up as $N$ goes to infinity. This means there exists an $N$ large enough so that $P\left(N\right) > 0\Rightarrow \binom{N}{2015} > 2015N^{2014}$.

Since there are more sums compared to the possible values for the sum, then by the pigeonhole principle, there exists at least two sums that have the same value.

PROBLEMS

10. Find all values of $x$, $y$, and $z$ such that $x^4+y^4+z^4-4xyz=-1$.
11. Find the number of ways to color $2015$ points on a circle with $3$ colors such that any two neighboring points have distinct colors.
12. Determine the minimum value of $\dfrac{a+b+c}{b-a}$ given that for all $x$, $ax^2+bx+c\geq 0$ and $a < b$.

We welcome readers to submit solutions to the problems posed below for publication consideration. Solutions may ONLY be submitted online via vantonio1992@gmail.com. Solutions must be preceded by the solver's name, school affiliation and year level. The deadline for submission is 12:30 PM October 10, 2015.

SOLUTIONS

(for September 26, 2015)

7. Let $ABCD$ be a rhombus with $\angle A=120^{\circ}$ and $P$ is any point on the plane of the rhombus. Prove that $$PA+PC >\frac{BD}{2}.$$ (Taken from Mathematical Olympiad Challenges (2nd Edition) by Andreescu and Gelca)
   (solved by Jarrett Ian G. Lim [Philippine Academy of Sakya], Carissa Elaine Varon [Falcon School], and Steven Reyes [Saint Jude Catholic School]; partial credit for Joyce Heidi Ong [Chiang Kai Shek College], Madeline L. Tee [Chiang Kai Shek College], and Trisha T. Huang [Chiang Kai Shek College])
   
   
   SOLUTION: 
   First we prove that given an equilateral triangle $XYZ$ and a point $P$ not on the circumcircle of this triangle, then we can construct a triangle with side lengths $PX$, $PY$, and $PZ$. Moreover, if $P$ lies on the circumcircle, then one of the three lengths is equal to the other two. This is known as Pompeiu's Theorem.
   
   We rotate $\triangle XYZ$ $60^{\circ}$ clockwise around $X$. As seen in the figure below, $Y$ will rotate to $Z$, while $Z'$ and $P'$ are images of $Z$ and $P$, respectively.
   
   

   

   
   Note that $P'Z$ is the image of $PY$. In addition, because of the rotation, $PP'X$ is an equilateral triangle, so $PP'$ is actually equal to $PX$. This means that we have $\triangle PP'Z$ as our desired triangle.
   
   If, on the other hand, $P$ is on the circumcircle, then we have the following figure.
   
   

   

   
   Note that if $P$ is on arc $XZ$, then $\angle ZPX$ is $120^{\circ}$. Because $\triangle PP'X$ is equilateral, then $\angle XPP'=60^{\circ}$, which means that $\angle ZPX$ and $\angle XPP'$ form a linear pair, so $Z$, $P$, and $P'$ are collinear.
   
   If $P$ is on arc $XYZ$, then $\angle ZPX=60^{\circ}$, and $\angle P'PX$ is also $60^{\circ}$ because $\triangle P'PX$ is equilateral. This means that $Z$, $P$, and $P'$ are collinear.
   
   This means that if $P$ is on arc $XZ$, then $$\begin{align} ZP' & = ZP+PP'\\ YP & = ZP+XP. \end{align}$$ If $P$ is on arc $XY$, then $$\begin{align} ZP & = ZP'+P'P\\ ZP & = YP+XP. \end{align}$$ And finally, if $P$ is on arc $YZ$, then $$\begin{align} PP' & = PZ+ZP'\\ XP & = ZP+YP. \end{align}$$ Now we go to the problem. Since $\angle A=120^{\circ}$, then $\angle B$ must be $60^{\circ}$. This means that $\triangle ABC$ is isosceles with vertex angle $60^{\circ}$, which implies that $\triangle ABC$ is equilateral.
   
   If $P$ is not on the circumcircle of $\triangle ABC$, then a triangle exists with sides $PA$, $PB$, and $PC$. This means that, by triangle inequality, $PA+PC > PB$. On the other hand, if $P$ is on the circumcircle of $\triangle ABC$, then $PA+PC=PB$. In general, we have $PA+PC\ge PB$.
   
   Similarly, since $\triangle ACD$ is also equilateral, we can have $PA+PC\geq PD$. Combining the two inequalities, we have $$2\left(PA+PC\right)\geq PB+PD.$$ Considering $\triangle PBD$, $PB+PD > BD$. This means that $$\begin{align} 2\left(PA+PC\right) & > BD\\ PA+PC & > \frac{BD}{2}. \end{align}$$
   
   
8. Determine, with proof, the values of $a$, $b$, and $c$, with $a < b < c$ such that $2015=a^{2}+b^{2}-c^{2}$. (Modified problem from 104 Number Theory Problems by Andreescu, Andrica, and Zuming)
   (solved by Jarrett Ian G. Lim [Philippine Academy of Sakya], Steven Reyes [Saint Jude Catholic School]; partial credit for Joyce Heidi Ong [Chiang Kai Shek College], Ryan Jericho Sy [Chiang Kai Shek College], and Madeline L. Tee [Chiang Kai Shek College])
   
   
   SOLUTION: 
   We prove this for a general value of $n$ and divide the solution into cases depending on the parity of $n$.
   
   If $n$ is even, then $n=2k$ for some $k$. Note that if $n=0$, then we have $$\begin{align} 0 & = a^{2}+b^{2}-c^{2}\\ c^{2} & = a^{2}+b^{2}, \end{align}$$ which means any Pythagorean Triple will hold. On the other hand, if $n=2$, then $$2=5^{2}+11^{2}-12^{2}.$$ Now, if $n\geq4$, that is, if $k > 1$, then $$5k-1 > 4k-1$$ and $$\begin{align} 1 & < k\\ 3k+1 & < 4k\\ 3k & < 4k-1. \end{align}$$ So now we have candidates $a=3k$, $b=4k-1$, and $c=5k-1$. It can be verified that $$\begin{align} \left(3k\right)^{2}+\left(4k-1\right)^{2}-\left(5k-1\right)^{2} & = 2k\\ & = n. \end{align}$$ Now we consider the case when $n$ is odd, then it can be written in the form $n=2k+1$. First, if $n=1$, then $$\begin{align} 1 & = 4^{2}+7^{2}-8^{2}\\ 3 & = 4^{2}+6^{2}-7^{2}\\ 5 & = 4^{2}+5^{2}-6^{2}\\ 7 & = 6^{2}+14^{2}-15^{2}. \end{align}$$ Now, if $k > 3$ (that is, $n > 7$), then, first,$5k-4 > 4k-4$. In addition, $$\begin{align} k & > 3\\ 4k & > 3k+3\\ 4k-4 & > 3k-1. \end{align}$$ This means that our candidates are $a=3k-1$, $b=4k-4$, and $c=5k-4$. It can be verified that $$\begin{align} \left(3k-1\right)^{2}+\left(4k-4\right)^{2}-\left(5k-4\right)^{2} & = 2k+1\\ & = n. \end{align}$$ In that case, if $n=2015=2\left(1007\right)+1$, then we just have $a=3020$, $b=4024$, and $c=5031$.
9. Consider $2015$ nonnegative real numbers $a_{1},a_{2},\dots,a_{2015}$ whose sum is $1$. Define $M$ to be $$M=\max_{1\leq k\leq}a_{k}+a_{k+1}+a_{k+2}.$$ As $a_{k}$ varies, $M$ varies as well. Find the minimum value of $M$. (Canadian Mathematical Olympiad, 1981)
   (partial credit for Jarrett Ian G. Lim [Philippine Academy of Sakya], Joyce Heidi Ong [Chiang Kai Shek College], and Madeline L. Tee [Chiang Kai Shek College])
   
   
   SOLUTION: 
   Since all the numbers are nonnegative, then $a_{1}\leq a_{1}+a_{2}\leq a_{1}+a_{2}+a_{3}$ and $a_{7}\leq a_{6}+a_{7}\leq a_{5}+a_{6}+a_{7}$. This means that $$\begin{align*} M & = \max_{1\leq k\leq2009}a_{k}+a_{k+1}+a_{k+2}.\\ & = \max_{1\leq k\leq2009}\left\{ a_{1},a_{1}+a_{2},a_{7},a_{6}+a_{7},a_{k}+a_{k+1}+a_{k+2}\right\} . \end{align*}$$ If we add all the 2013 quantities, we have $$\begin{align*} \text{sum} & = a_{1}+\\ & \left(a_{1}+a_{2}\right)+\\ & \left(a_{1}+a_{2}+a_{3}\right)+\\ & \left(\hphantom{a_{1}+}a_{2}+a_{3}+a_{4}\right)+\\ & \vdots\\ & \left(a_{2009}+a_{2010}+a_{2011}\right)+\\ & \left(\hphantom{a_{2009}+}a_{2010}+a_{2011}\right)+\\ & \left(\hphantom{a_{2009}+a_{2010}+}a_{2011}\right)\\ & = 3\left(a_{1}+a_{2}+\cdots+a_{2011}\right)\\ & = 3. \end{align*}$$ We then take the average of these 2013 quantities, and we get $\dfrac{3}{2013}=\dfrac{1}{671}$. If all the quantities are less than $\dfrac{1}{671}$, then the average should be less than $\dfrac{1}{671}$. This means that at least one quantitity should be greater than or equal to $\dfrac{1}{671}$. This implies that $M\geq\dfrac{1}{671}$. This means that the minimum value for $M$ is $\dfrac{1}{671}$. Specifically, this can be achieved by letting $a_{k}=\dfrac{1}{671}$ if $k\equiv1\mod3$, and $a_{k}=0$ otherwise.

ERRATA

Madeline L. Tee [Chang Kai Shek College] and Carissa Elaine Varon [Falcon School] were not properly recognized for their solutions to the questions from the previous weeks. The previous issues have been updated to rectify this error.