2016 AIME II Problem 15

Question

For

1 \le i \le 215

let

a_i = \frac{1}{2^i}

and

a_{216} = \frac{1}{2^{215}}.

Let

x_1,

x_2,

\ldots,

x_{216}

be positive real numbers such that

\sum_{i=1}^{216} x_i = 1

and

\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

x_2 = \frac{m}{n},

where

m

and

n

are relatively prime positive integers. Find

m + n.

Answer

Use

2\sum_{i \lt j} x_i x_j = 1 - \sum x_i^2

to turn the condition into

\sum \frac{x_i^2}{1 - a_i} = \frac{1}{215}

Since

\sum (1 - a_i) = 215,

Cauchy-Schwarz makes this an equality case, forcing

x_i

proportional to

1 - a_i

Since

\sum x_i = 1,

we have

2\sum_{i \lt j} x_i x_j = 1 - \sum x_i^2.

Doubling the given equation and rearranging,

\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

\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

\sum a_i = \left(\frac{1}{2} + \cdots + \frac{1}{2^{215}}\right)

+ \frac{1}{2^{215}} = 1,

so

\sum (1 - a_i) = 216 - 1 = 215.

By the Cauchy-Schwarz inequality,

\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

x_i

is proportional to

1 - a_i,

forcing

x_i = \frac{1 - a_i}{215}.

The only, hence maximum, possible value of

x_2

is

\frac{1 - \frac{1}{4}}{215} = \frac{3}{860},

and

m + n = 3 + 860 = 863.

Problem 15 in other years