wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Vectors
        
(Message started by: THUDandBLUNDER on Jan 9^th, 2004, 12:30am)

Title: Vectors
Post by THUDandBLUNDER on Jan 9^th, 2004, 12:30am

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?

Title: Re: Vectors
Post by towr on Jan 9^th, 2004, 12:57am

::[hide]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.[/hide]::

Title: Re: Vectors
Post by THUDandBLUNDER on Jan 9^th, 2004, 6:01am

Good point, perspicacious towr.

Assume we are considering only non-empty proper subsets of a finite set.

Title: Re: Vectors
Post by rmsgrey on Jan 9^th, 2004, 7:11am

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...

Title: Re: Vectors
Post by THUDandBLUNDER on Jan 9^th, 2004, 9:21am

I thought that I could write out the question clearly in one sentence, but obviously not.

Let a set of vectors {V₁, V₂, ...V_n} be 'one-summable' if |V₁| + |V₂ +.......+ |V_n| = 1.
Excluding the empty set, a 'one-summable' set with n vectors has 2ⁿ - 1 subsets.
The k vectors in each subset can be added to get a vector with a certain length m, say.
That is, |v₁ + v₂......+......+ v_k| = m (for k = 1 to n)
So each 'one-summable' vector set produces 2ⁿ - 1 values for m.

Let m_max = M
What is M_min?

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?

Title: Re: Vectors
Post by Eigenray on Jan 10^th, 2004, 12:27am

Answer: [hide]1/pi[/hide] :
Hint: [hide]Sort the vectors by angle[/hide], then [hide]draw each vector starting at the tip of the previous one[/hide].
Solution: [hide]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[/hide].

Conversely, consider [hide]n equally spaced vectors, and let n go to infinity. Then the maximal subset's sum has norm approaching 1/pi[/hide].

Title: Re: Vectors
Post by Barukh on Jan 11^th, 2004, 11:27am

Let me repeat it again, Eigenray: absolutely brilliant :D !

Don't you agree, THUD&BLUNDER?