Consider a set of positive real numbers $\{P_1,P_2,\dots,P_n\}$ and a permutation of this set $\{Q_1,Q_2,\dots,Q_n\}$.

Is it possible to find a permutation such that $$\sum_{i=1}^n\frac{P_i}{Q_i}<n$$?

We can prove that for $n=2$ the statement is incorrect and assume that for $n=k$ the statement is correct and we should prove for $n=k+1$.

  • 2
    $\begingroup$ A permutation such that $\sum \frac{P_i}{Q_i}$ .... what? $\endgroup$ – David Peterson Dec 21 '14 at 11:49
  • $\begingroup$ flagged "unclear what you are asking" $\endgroup$ – Dheeraj Kumar Dec 21 '14 at 11:51
  • $\begingroup$ "Is it possible to find a permutation such that sum(Pi/Qi)"... this is half of a question... $\endgroup$ – 5xum Dec 21 '14 at 11:52

The geometric mean of those $n$ ratios is $1$. Therefore their arithmetic mean is at least $1$. Therefore their sum is at least $n$.

  • $\begingroup$ Thanks a lot for your guide $\endgroup$ – Meh Dec 21 '14 at 12:31

If you can prove that the statement is incorrect for $n=2$, then that is all you need to do. The statement is false, period.

  • $\begingroup$ I want to use Induction algorithm and I prove that for n=2 the statement is incorrect but I cannot continue it could you help me? $\endgroup$ – Meh Dec 21 '14 at 12:12
  • $\begingroup$ @Meh If the statement is untrue for $n=2$, then the statement "this statement is true for all $n$" is false. No induction needed. $\endgroup$ – 5xum Dec 21 '14 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.