Author |
Topic: Vectors (Read 289 times) |
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
Given a finite set S of 2D vectors whose absolute magnitudes sum to 1, what is the maximum value of x such that for every S there exists a subset of S whose sum has absolute magnitude x?
|
| « Last Edit: Jan 9th, 2004, 8:33am by ThudnBlunder » |
 IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
 |
Re: Vectors
« Reply #1 on: Jan 9th, 2004, 12:57am » |
 Quote  Modify
|
::since S is a subset of S, I would say x=1
If you want to have a proper subset (one which is smaller than the original set) then x=0, since S could have just one element, and the only proper subset would be the empty set and a sum over an empty domain is 0.::
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Vectors
« Reply #2 on: Jan 9th, 2004, 6:01am » |
Quote Modify
|
Good point, perspicacious towr.
Assume we are considering only non-empty proper subsets of a finite set.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Vectors
« Reply #3 on: Jan 9th, 2004, 7:11am » |
Quote Modify
|
Then Towr's set still kills the problem - it has no non-empty proper subsets, and satisfies all conditions placed on S so there is no such number x...
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Vectors
« Reply #4 on: Jan 9th, 2004, 9:21am » |
Quote Modify
|
I thought that I could write out the question clearly in one sentence, but obviously not.
Let a set of vectors {V1, V2, ...Vn} be 'one-summable' if |V1| + |V2 +.......+ |Vn| = 1.
Excluding the empty set, a 'one-summable' set with n vectors has 2n - 1 subsets.
The k vectors in each subset can be added to get a vector with a certain length m, say.
That is, |v1 + v2......+......+ vk| = m (for k = 1 to n)
So each 'one-summable' vector set produces 2n - 1 values for m.
Let mmax = M
What is Mmin?
In other words, given a set of vectors such that the sum of the magnitudes of those vectors sums to 1, we need to choose a subset of those vectors which maximizes the magnitude of the sum. What is that maximum?
|
| « Last Edit: Jan 9th, 2004, 9:32am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Vectors
« Reply #5 on: Jan 10th, 2004, 12:27am » |
Quote Modify
|
Answer: 1/pi :
Hint: Sort the vectors by angle, then draw each vector starting at the tip of the previous one.
Solution: Complete to form a closed, convex polygon, so that the vectors sum to zero. Then the circumference C of this polygon will be no more than pi times its diameter D. So D >= C/pi >= 1/pi. But the diameter is precisely the sum of a subset of these vectors.
Conversely, consider n equally spaced vectors, and let n go to infinity. Then the maximal subset's sum has norm approaching 1/pi.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Vectors
« Reply #6 on: Jan 11th, 2004, 11:27am » |
Quote Modify
|
Let me repeat it again, Eigenray: absolutely brilliant  !
Don't you agree, THUD&BLUNDER?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print