Minimise the sum of ratios

Question

I have a list $a$ whose elements are positive real values. Assume $a_i > a_2 > ... a_{n-1} > a_n$, and assume $n$ is even. You must form unique pairs from $a$ and for each pair's value is given by $\frac{a_i}{a_j}$, and $a_i < a_j$. The goal is to minimise the sum of these ratios, and for each solution the pairs must be unique and each element can be chosen only once. Example, $a = \{4,3,2,1\}$. There are three possible solutions, and one of them is $S = \frac{1}{2} + \frac{3}{4}$.

If this is a well known problem, I apologise, and if so I would like to be directed to material or other similar questions that would help.

Answer 1

Hints towards a solution. If you're stuck, explain what you've tried.

Prove the following "obvious" statements:

• We want to minimize the numerators and maximize the denominators, so the numerators should be $ \{ a_n, a_{n-1} \ldots a_{n/2 + 1 } \}$ and the denominators should be $ \{ a_1, a_2, \ldots, a_n\}$.
• The minimum occurs at

$$ \sum_{i=1}^{n/2} \frac{ a_{n/2 + i} } { a_{0+i} } $$

EG For the $a = \{4, 3, 2, 1 \}$ case, the minimum is $\frac{1}{3} + \frac{2}{4}$.

One approach is to:

Apply the rearrangement inequality