2011 AIME II Problems/Problem 9

Problem 9

Let $x_1, x_2, ... , x_6$ be non-negative real numbers such that $x_1 +x_2 +x_3 +x_4 +x_5 +x_6 =1$ , and $x_1 x_3 x_5 +x_2 x_4 x_6 \ge {\scriptstyle\frac{1}{540}}$ . Let $p$ and $q$ be positive relatively prime integers such that $\frac{p}{q}$ is the maximum possible value of $x_1 x_2 x_3 + x_2 x_3 x_4 +x_3 x_4 x_5 +x_4 x_5 x_6 +x_5 x_6 x_1 +x_6 x_1 x_2$ . Find $p+q$ .

Solution

Note that neither the constraint nor the expression we need to maximize involves products $x_i x_j$ with $i - j \equiv 3 \pmod 6$ . Factoring out say $x_1$ and $x_4$ we see that the constraint is $x_1(x_3x_5) + x_4(x_2x_6) \ge {\scriptstyle\frac1{540}}$ , while the expression we want to maximize is $x_1(x_2x_3 + x_5x_6 + x_6x_2) + x_4(x_2x_3 + x_5x_6 + x_3x_5)$ . Adding the left side of the constraint to the expression we get: $(x_1 + x_4)(x_2x_3 + x_5x_6 + x_6x_2 + x_3x_5) = (x_1 + x_4)(x_2 + x_5)(x_3 + x_6)$ . This new expression is the product of three non-negative terms whose sum is equal to 1. By AM-GM this product is at most $\scriptstyle\frac1{27}$ . Since we have added at least $\scriptstyle\frac1{540}$ the desired maximum is at most $\scriptstyle\frac1{27} - \frac1{540} = \frac{19}{540}$ . It is easy to see that this upper bound can in fact be achieved by ensuring that constraint expression is equal to $\scriptstyle\frac1{540}$ with $x_1 + x_4 = x_2 + x_5 = x_3 + x_6 = \scriptstyle\frac13$ —for example, by choosing $x_1$ and $x_2$ small enough—so our answer is $540 + 19 = \fbox{559}.$