Let $A=\{|a_i|:a_i\in\mathbb{Z}\land1\leq i\leq n\}$ and $n\geq 1$
Let $b_i=\frac{\max A}{|a_i|}.$
How can one prove that the minimum possible value for$\sum\limits_{i=1}^n b_i$ is $n$?
Asked
Active
Viewed 55 times
2 Answers
0
It is not true. Let $A=\{1,2\}$, then $b=(2,1)$ and the sum is $3$. In fact it will only be true if all the $a_i$ are the same.
Ross Millikan
- 374,822
-
Sorry for the typo. The question meant to prove that no matter what set $A$ you choose, you'll never get $\sum\limits_{i=1}^n b_i$ less than $n+1$ where $n$ is the number of elements in $A$. – Maazul May 04 '13 at 03:34
-
@Maazul: Now it fails if $A$ has only one element. It also fails if $A={1000,1001,1002}$ – Ross Millikan May 04 '13 at 03:39
-
I'm really having a bad day today... Excuse me, this is the final edit: $n\geq 1$ and minimum for $\sum\limits_{i=1}^n b_i$ is really $n$. – Maazul May 04 '13 at 03:44
-
Please confirm if you observe any case where the condition still fails. – Maazul May 04 '13 at 03:45
-
1@Maazul: Then each $b_i \ge 1$ so it is true and easy – Ross Millikan May 04 '13 at 03:47
-
That was obvious... I feel dumb now. – Maazul May 04 '13 at 04:17
0
The harmonic mean of positive numbers $x_1,\dots, x_n$ is defined as $$\frac{n}{\frac{1}{x_1}+\cdots+\frac{1}{x_n}}.$$ A modestly important inequality, known to generations of contest kids as AM/HM, states that the harmonic mean is never bigger than the arithmetic mean. The required result is a direct consequence of that.
To get rid of the irrelevant absolute values, let the $a_i$ be positive. Let $a=\max a_i$ and let $x_i=\frac{a_i}{a}$. Then we have, by taking the reciprocal of the harmonic mean, that $$\frac{\frac{a}{a_1}+\cdots\frac{a}{a_n}}{n}\ge \frac{n}{\frac{a_1}{a}+\cdots+\frac{a_n}{a}}.$$ But the $a_i$ are $\le a$, so $\sum \frac{a_i}{a}\le n$, and the inequality follows.
Remark: We leave the silly (but correct) proof above as a lesson in look before you leap. For of course there is a far simpler proof.
André Nicolas
- 507,029