2016 AIME II Problem 15

Attempt Problem 15 of the 2016 AIME II below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2016 AIME II solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

15.

For 1i2151 \le i \le 215 let ai=12ia_i = \frac{1}{2^i} and a216=12215.a_{216} = \frac{1}{2^{215}}. Let x1,x2,,x216x_1, x_2, \ldots, x_{216} be positive real numbers such that i=1216xi=1\sum_{i=1}^{216} x_i = 1 and 1i<j216xixj=107215+i=1216aixi22(1ai). \begin{aligned} &\sum_{1 \le i \lt j \le 216} x_i x_j \\ &= \frac{107}{215} \\ &\quad {}+ \sum_{i=1}^{216} \frac{a_i x_i^2}{2(1 - a_i)}. \end{aligned} The maximum possible value of x2=mn,x_2 = \frac{m}{n}, where mm and nn are relatively prime positive integers. Find m+n.m + n.

Answer: 863
Concepts:Cauchy-Schwarz Inequalityinequalityalgebraic manipulation
Difficulty rating: 3500
Solution:

Since xi=1,\sum x_i = 1, we have 2i<jxixj=1xi2.2\sum_{i \lt j} x_i x_j = 1 - \sum x_i^2. Doubling the given equation and rearranging, 1i=1216xi2=214215+i=1216aixi21ai, \begin{aligned} 1 - \sum_{i=1}^{216} x_i^2 &= \frac{214}{215} \\ &\quad {}+ \sum_{i=1}^{216} \frac{a_i x_i^2}{1 - a_i}, \end{aligned} so 1215=i=1216(1+ai1ai)xi2=i=1216xi21ai. \begin{aligned} \frac{1}{215} &= \sum_{i=1}^{216}\left(1 + \frac{a_i}{1 - a_i}\right)x_i^2 \\ &= \sum_{i=1}^{216} \frac{x_i^2}{1 - a_i}. \end{aligned}

Now ai=(12++12215)\sum a_i = \left(\frac{1}{2} + \cdots + \frac{1}{2^{215}}\right) +12215=1,+ \frac{1}{2^{215}} = 1, so (1ai)=2161=215.\sum (1 - a_i) = 216 - 1 = 215. By the Cauchy-Schwarz inequality, 1=(i=1216xi)2(i=1216xi21ai)(i=1216(1ai))=1215215=1. \begin{aligned} 1 &= \left(\sum_{i=1}^{216} x_i\right)^2 \\ &\le \left(\sum_{i=1}^{216} \frac{x_i^2}{1 - a_i}\right) \\ &\quad {}\cdot \left(\sum_{i=1}^{216} (1 - a_i)\right) \\ &= \frac{1}{215} \cdot 215 = 1. \end{aligned}

Equality holds, so xix_i is proportional to 1ai,1 - a_i, forcing xi=1ai215.x_i = \frac{1 - a_i}{215}. The only, hence maximum, possible value of x2x_2 is 114215=3860,\frac{1 - \frac{1}{4}}{215} = \frac{3}{860}, and m+n=3+860=863.m + n = 3 + 860 = 863.

← Problem 14#14
Full Exam

Problem 15 in Other Years