MathDB
a_\pi(1)/ b_\pi(1)} <a_\pi(2)/ b_\pi(2)} < ...< a_\pi(n)/ b_\pi(n)}

Source: 7th QEDMO problem 8 (14. - 17. 1. 2010) https://artofproblemsolving.com/community/c1512515_qedmo_200507

May 9, 2021
algebrainequalities

Problem Statement

Let (a1,a2,...,an)(a_1, a_2,..., a_n) and (b1,b2,...,bn)(b_1, b_2, ..., b_n) be two sequences of positive real numbers. Let π\pi be a permutation of the set {1,2,...,n}\{1, 2, ..., n\}, for which the sum aπ(1)(bπ(1)+bπ(2)+...+bπ(n))+aπ(2)(bπ(3)+bπ(3)+...+bπ(n))+...+aπ(n)bπ(n)a_{\pi(1)}(b_{\pi(1)}+b_{\pi(2)}+...+b_{\pi(n)})+a_{\pi(2)}(b_{\pi(3)}+b_{\pi(3)}+...+b_{\pi(n)})+...+a_{\pi(n)}b_{\pi(n)} is minimal. Proce for this permutation π\pi, that aπ(1)bπ(1)≤aπ(2)bπ(2)≤...≤aπ(n)bπ(n) \frac{a_{\pi(1)}}{b_{\pi(1)}}\le \frac{a_{\pi(2})}{b_{\pi(2)}}\le ... \le \frac{a_{\pi(n)}}{b_{\pi(n)}}
Application: In an idealized role-playing game you fight against nn opponents at the same time. In order to minimize the damage you suffer yourself, you should first take care of your opponent for the ratio of the time it takes to defeat him (if you only focus on him), and the damage it does per second is minimal; next, one should fight the opponent with the second smallest such ratio, and so on.
Back to ProblemsView on AoPS