Tuesday, August 19, 2014

Optimal Proof - Nisoku in SRM 463

I'll prove a subtle part of the problem:

Given a sorted array of even length $latex \{a_1, a_2, \ldots, a_{2n}\}$, we need to pair these elements and multiply the sum of each pair. The largest value should be $latex (a_1 + a_{2n}) \times (a_2 + a_{2n-1}) \cdots$.

Let's consider an easier case. Suppose we have 4 numbers $latex a<b<c<d$. It's obvious that $latex (a+d)(b+c)>(a+b)(c+d)$ and $latex (a+d)(b+c)>(a+c)(b+d)$. How can we generalize this property?

Suppose $latex a_1$ is paired with some $latex a_i$, and $latex a_{2n}$ is paired with some $latex a_j$. By a single exchange, we could get a better solution. After that, the pair of the smallest & largest element remains the same, and we can use induction here for inner elements.

Sometimes it's just essential to prove pairwise inequalities for sequence optimality.