Problem:
For 1≤i≤215 let ai=2i1 and a216=22151. Let x1,x2,…,x216 be positive real numbers such that
i=1∑216xi=1 and 1≤i<j≤216∑xixj=215107+i=1∑2162(1−ai)aixi2
The maximum possible value of x2=nm, where m and n are relatively prime positive integers. Find m+n.
Solution:
For 1≤i≤216, let bi=1−ai. Because ∑i=1216ai=1, it follows that ∑i=1216bi2=215. Also, if {xi} is a sequence of positive real numbers with ∑i=1216xi=1, then ∑1≤i<j≤2162xixj=(∑i=1216xi)2−∑i=1216xi2=1−∑i=1216xi2.
Observe that for each i,(bixi)2−2152xi+(215bi)2=(bixi−215bi)2≥0, and thus summing over 1≤i≤216 yields ∑i=1216((bixi)2−2152xi+(215bi)2)≥0. Because ∑i=1216bi2=215 and ∑i=1216xi=1, it follows that ∑i=1216(bixi)2−2152+21521⋅215≥0, which is equivalent to 2151≤∑i=1216(bixi)2=∑i=12161−aixi2. Hence ∑1≤i<j≤2162xixj=1−∑i=1216xi2≤215214+∑i=12161−aixi2−∑i=1216xi2=215214+∑i=12161−aiaixi2, so ∑1≤i<j≤216xixj≤215107+∑i=12162(1−ai)aixi2.
Equality occurs in this inequality if and only if for each i,bixi−215bi=0 or xi=2151−ai. Therefore such a sequence {xi} is unique and x2=8603. The requested sum is 3+860=863.