Author |
Topic: Product of distances (Read 762 times) |
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
 |
Product of distances
« on: Jun 4th, 2005, 12:28pm » |
 Quote  Modify
|
Given n points on the unit circle, let M denote the maximum, over all z on the unit circle, of the product of the distances from z to the other n points, i.e.,
M = max|z|=1 [prod] |z-zi|.
What is the best lower bound for M?
When is it obtained?
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Product of distances
« Reply #1 on: Jun 4th, 2005, 1:17pm » |
Quote Modify
|
Intuitively, I would say the points must be equally spaced on the circle.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Product of distances
« Reply #2 on: Jun 4th, 2005, 11:22pm » |
Quote Modify
|
And it looks like the answer is 2, although I haven't come up with an argument yet.
Another nifty fact is that the product of the distances from one of the vertices to the other n-1 is n. (when they're equally spaced)
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Product of distances
« Reply #3 on: Jun 5th, 2005, 1:04pm » |
Quote Modify
|
Deedlit is right: the minimum possible value of the maximum is 2
Here is why:
| hidden: |
Let the n points be zi i = 1 to n.
We can rotate the circle so that (-1)n[prod]zi = 1.
Now consider
P(z) = (z-z1)(z-z2)...(z-zn)
We are interested in |P(z)| for various z on the unit circle.
Let wi be the nth roots of unity.
Consider [sum] P(wi)
Since [sum]i wik = 0, 1 [le] k [le] n-1, we have that [sum] P(wi) = 2n.
Thus [sum] |P(wi)| [ge] |[sum] P(wi)| = 2n.
Hence, for some i, |P(wi)| [ge] 2.
It can be shown that for the n points which are equally spaced, the maximum value of |P(z)| is 2.
|
|
| « Last Edit: Jun 5th, 2005, 1:06pm by Aryabhatta » |
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Product of distances
« Reply #4 on: Jun 5th, 2005, 8:56pm » |
Quote Modify
|
Sweet! As for proving the bound strict,
| hidden: |
We can use the fact that sin(x) sin(c - x), with 0 <= x <= c, is maximized when x = c / 2. Assuming that the zi are equally spaced, choose z so that it bisects the arc between z1 and z2. The length |z - zi| = 2 sin (theta/2), where theta is the difference between the arguments of z and zi. So, we divide the zi into pairs for which the angles are the same. (when n is odd, there is one zi that is diametrically opposed to z.) For each such pair zm and zn, the value of |z - zm| |z - zn| is maximized by the current value of z, by the lemma from the beginning. And, of course, |z - zi| for the diametrically opposite zi as at its maximum value. So the product of all the |z - zi| is certainly maximized.
All that's left is to show that the above product is 2. However, I haven't been able to come up with a slick proof of that. It does follow from the fact I mentioned earlier (that the product of the distances from one of the zi to the others is n.)
|
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Product of distances
« Reply #5 on: Jun 6th, 2005, 1:20am » |
Quote Modify
|
There is a simpler proof in case of the equally spaced version:
| hidden: |
The given points are wi, the nth roots of unity.
P(z) = Prod (z-wi) = zn - 1. (as they are the roots of unity)
|P(z)| = |zn - 1| [le] |zn| + 1 = 2.
Any root of zn + 1 = 0 will suffice to achieve the maximum of 2.
|
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Product of distances
« Reply #6 on: Jun 6th, 2005, 9:51pm » |
Quote Modify
|
Yeah, that's a little slicker, although the idea of maximizing pairs of distances is pretty immediate conceptually - it just takes a little longer to write down.
And now I see the same method works for the other problem:
| hidden: |
The product of the distances to all nth roots of unity except 1 is
P(z) = (zn - 1) / (z - 1) = zn-1 + zn-2 + ... + z + 1.
and P(1) = 1 + 1 + ... + 1 = n.
|
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Product of distances
« Reply #7 on: Jun 11th, 2005, 10:46am » |
Quote Modify
|
Nice job. It just remains to be shown that if M=2, then the points are equally spaced.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Product of distances
« Reply #8 on: Jun 12th, 2005, 1:27pm » |
Quote Modify
|
Ahh.. there seemed to be something missing..
Here is a demonstration that if M=2, then the points are equally spaced:
| hidden: |
Assume points are z1,z2,...,zn such that their product is (-1)n.
Consider P(z) = (z-z1)(z-z2)...(z-zn) = zn + 1 + Q(z)
We would like to show that Q(z) = 0 for all z.
As before consider the values at w1, w2,...,wn the nth roots of unity.
Since M = 2,
We have that |P(wi)| = 2 exactly.
(because [sum]|P(wi)| = 2n and M=2.)
i.e |2 + Q(wi)| = 2 for each i. -- (1)
We also have that [sum] Q(wi) = 0.
(1) says that each Q(wi) lies on the circle of radius 2 centred at (-2,0). Sum of any points on that circle can never be zero, unless they all are zero. (as all points have non-positive x co-ordinates.)
Thus we must have that Q(wi) = 0 for each i. Since Q(z) is a polynomial of degree n-1 we have that it is identically zero.
|
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Product of distances
« Reply #9 on: Jun 14th, 2005, 1:12am » |
Quote Modify
|
Well done.
| hidden: |
In fact, since [sum] P(wi) = 2n, we have immediately that P(wi) = 2 for all i if M = 2.
|
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Product of distances
« Reply #10 on: Jun 14th, 2005, 10:17am » |
Quote Modify
|
on Jun 14th, 2005, 1:12am, Deedlit wrote:Well done.
| hidden: |
In fact, since [sum] P(wi) = 2n, we have immediately that P(wi) = 2 for all i if M = 2.
|
|
|
Aah.. if P(wj) = xj + iyj then [sum] xj = 2n. We must also have that |xj| [le] 2. It follows that each must be 2. From which it follows that yj = 0.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print