wu :: forums - Print Page


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

        riddles >> putnam exam (pure math) >> Distinct Dot Products
        
(Message started by: william wu on Sep 29^th, 2004, 3:32pm)

Title: Distinct Dot Products
Post by william wu on Sep 29^th, 2004, 3:32pm

This is a problem I accidentally made up. Not sure how to solve it ... maybe it is interesting.

Given a fixed nx1 vector of naturals V, how many distinct dot products S.V exist, where S is an nx1 vector over {-1,+1}?

In other words, if I have to add up a bunch of numbers, how many distinct sums can I make if I'm allowed to twiddle with their signs? My first response was orbit-stabilizer theorem, but I can't figure out the group action.

Title: Re: Distinct Dot Products
Post by Aryabhatta on Sep 29^th, 2004, 4:54pm

I think it is NP-complete to even determine if the number of distinct sums is 2ⁿ or not. It seems to be equivalent to the subset sum = 0 problem considering the set to be the of 2n numbers with + and - signs.

I doubt if there will be a 'simple' closed form solution to this.
There sure could be closed forms solutions. But those most likely could not be evaluated in polynomial time.

Just thought it might be relevant. Sorry if it is not.

Title: Re: Distinct Dot Products
Post by Aryabhatta on Sep 30^th, 2004, 10:51am

Sorry, the 2n numbers have a trivial subset which sums to zero. Maybe there is an different form of the subset sum problem which applies here.

Title: Re: Distinct Dot Products
Post by Barukh on Oct 10^th, 2004, 1:31am

on 09/29/04 at 16:54:50, Aryabhatta wrote:

IMHO, even the problem of determining if a particular sum s may be achieved as a described dot-product is NP-complete, since it’s equaivalent to a Knapsack Problem (http://mathworld.wolfram.com/KnapsackProblem.html) with sum = (N+s)/2, where N is the sum of all numbers in V.

Title: Re: Distinct Dot Products
Post by william wu on Oct 24^th, 2004, 10:36am

Interesting, although my problem may be easier than determining if a particular sum is possible, since I dont require any specific information aside from the number of possibilities.

Title: Re: Distinct Dot Products
Post by Aryabhatta on Oct 25^th, 2004, 2:53pm

on 10/24/04 at 10:36:14, william wu wrote:

Interesting, although my problem may be easier than determining if a particular sum is possible, since I dont require any specific information aside from the number of possibilities.

It is NP-complete even to decide if the number of distinct sums is Odd or Even.

Here is a proof.

Fact 1) PARTITION is NP-Complete.
PARTITION: Given integers c₁, ..., c_n, does there exist an S [subseteq] {1,2,...,n} such that [sum]_j[in]Sc_j = [sum]_j[notin]Sc_j.

We can easily show the PARTITION remains NP-complete even if c_i's are all assumed to be positive.

Fact 2) Give an nx1 vector V of natural numbers, the number of distinct dot products S.V where S is an arbitrary vector over {-1,+1} is odd if an only if there is some S' (over {-1,+1}) such that V.S' = 0.

Proof of Fact 2) Let {A₁, ..., A_k} be the set of distinct dot products. Clearly -A₁,...,-A_k are also part of the same set. So we can pair off the non-zero dot products, with their negatives. Thus k is odd if and only if 0 is in the set. []

Now V has a partition if and only if there is some S' such that V.S' = 0.

Thus V has a partition if and only if the number of distinct dot products is odd and hence determining the parity of the number of distinct dot products is NP-Complete.

Title: Re: Distinct Dot Products
Post by william wu on Oct 25^th, 2004, 11:58pm

Bravo Aryabhatta! In playing with the problem, I had also observed that {-A1,...,-Ak} are part of the same set, but you found a way to really capitalize on this fact. Thanks.