[Search for users]
[Overall Top Noters]
[List of all Conferences]
[Download this site]
| Title: | Mathematics at DEC |
|
| Moderator: | RUSURE::EDP |
|
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
1645.0. "Crux Mathematicorum 1742" by BEING::EDP (Always mount a scratch monkey.) Wed Jul 15 1992 12:52
Here's a problem from _Crux Mathematicorum_.
-- edp
1742. Proposed by Murray S. Klamkin, University of Alberta.
Let 1 <= r < n be integers and x[r+1], x[r+2], . . ., x[n] be given
positive real numbers. Find positive x[1], x[2], . . ., x[r] so as to
minimize the sum
S = sum x[i]/x[j]
taken over all i and j in { 1, 2, 3, . . ., n } with i != j.
(This problem is due to Byron Calhoun, a high school student in McLean,
Virginia. It appeared, with solution, in a science project of his.)
| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 1645.1 | | SSAG::LARY | Laughter & hope & a sock in the eye | Wed Jul 15 1992 23:17 | 13 |
| This is equivalent to minimizing
a*sum(Xi) + b*sum(1/Xi) + sum(Xi)*sum(1/Xi)
where the sums run from 1 to r, and
a = sum(1/Xi) for i = r+1 to n
b = sum(Xi) for i = r+1 to n
Obviously if r = 1 then the (single) new x1 that minimizes the desired sum
is x1 = sqrt(b/a), and in fact you can't go too far wrong in the general
case by setting all the Xi equal to sqrt(b/a), but I don't think that's the
general minimum...
|
| 1645.2 | | DESIR::BUCHANAN | | Fri Jul 17 1992 08:47 | 32 |
| We want to minimize:
f = sum(Xi) * sum(1/Xi) where sums are from 1..n.
df/dXj = sum(1/Xi) - sum(Xi)/Xj^2 for j=1..r.
If df/dxj = 0, then:
Xj^2 = sum(Xi)/sum(1/Xi) for j = 1..r.
ie. Xj = X for j=1...r.
Let sum(j=r+1..n)(Xi) = a
Let sum(j=r+1..n)(1/Xi) = b
rX^2 = (a+rX)/(b+r/X)
=> brX^2 + (r^2-r)X - a = 0
=> X = [1-r +/- _/[(1-r)^2 + 4ab/r]]/2b
But is this unique extremum minimal? Since r < n, if we allow any
X_j to tend to zero or infinity, the value of f will go to infinity. So
all boundaries to the domain are maxima. I could say loosely that "by
elimination" the unique finite extremum that we've found must be a minimum,
but the right approach is to show that M, the matrix of second derivatives, is
+ve definite.
The diagonal terms are:
-2/Xj^2 + 2*(a+sum(Xi))/Xj^3
while the off-diagonal terms are:
-1/Xj^2 -1/Xk^2
Is there anyone who can see that it's "obvious" that A is +ve definite?
Andrew.
|
| 1645.3 | final tidy-up | DESIR::BUCHANAN | | Fri Jul 17 1992 10:53 | 14 |
| > The diagonal terms are:
> -2/Xj^2 + 2*(a+sum(Xi))/Xj^3
> while the off-diagonal terms are:
> -1/Xj^2 -1/Xk^2
>
> Is there anyone who can see that it's "obvious" that M is +ve definite?
Yes, it's obvious. Xj = X, for j=1..r.
If you take some random vector p = (p1..pr)', and compute p'Mp, you
get a*(something +ve) + (2/X^2)*[sum(1)sum(pi^2)-sum(pi)^2], and the stuff in
square brackets is +ve by the Schwartz inequality. So that's it.
Andrew.
|