Subsequence that Sums Up to Half the Total Sum

[TCAZN]

Hi all,

I was just looking at the U.S. electoral map, and I was wondering if there could possibly be a tie in presidential elections (the answer is probably no). I tried to think of an efficient algorithm to answer this question, but due to my limited intelligence and imagination, all I could think of is the brute force method. I guess in this particular problem, efficiency probably does not matter since the number of states definitely doesn't follow any kind of Moore's Law.

Anyways, I was just wondering if anyone knows an efficient algorithm for the following problem:

Given a finite sequence $$a_1, a_2, \dots a_n,$$ determine whether there is a sub-sequence $$a_{i_1}, a_{i_2}, \dots a_{i_k}$$ such that $$\sum_{j=1}^{k} a_{i_j} = \frac{1}{2} \sum_{j=1}^{n}a_j$$.

 

[willem2]

Google for "knapsack problem"

In this case, there are 2^51 combinations of states and only 500 or so possible values,
so it's almost certain some combination has half the votes. (unless the total number of votes is odd)
Just select states at random with a coin flip and you'll get it within a few thousand tries.

 

[micromass]

According to the New York Times’ FiveThirtyEight blog, one possible scenario to give each candidate 269 electoral votes would be if President Obama wins the following:

Washington, D.C.
California
Oregon
Washington
Hawaii
New Mexico
Minnesota
Michigan
Illinois
Wisconsin
Ohio
Pennsylvania
Maryland
Delaware
New Jersey
New York
Connecticut
Massachusetts
Rhode Island
New Hampshire
Vermont
Maine

Under that scenario, Gov. Romney would win all other states, including battleground states like Florida, Iowa, Virginia, Colorado and Nevada. The FiveThirtyEight blog pegs the chance of a tie occurring at 1.3%.

Source: http://foxnewsinsider.com/2012/10/24/what-happens-if-the-presidential-election-ends-in-a-tie/

 

[Edgardo]

Look up the partition problem. It seems that it can be solved with dynamic programming.

 

[LudusRex]

Hello,

Thank you for bringing up this interesting problem and for sharing your thoughts on it. I can understand your concern about finding an efficient algorithm for this problem. While I cannot provide a specific algorithm, I can offer some insights and suggestions that may help in finding a solution.

Firstly, let's clarify that a tie in a presidential election is possible, although it is rare. In the event of a tie, the election is decided by the House of Representatives. Now, coming to the problem at hand, finding a subsequence that sums up to half the total sum is essentially a subset sum problem, which is a well-known problem in computer science with various known solutions.

One approach to solving this problem is by using dynamic programming, where we can keep track of the partial sums and check if any of them is equal to half the total sum. This approach has a time complexity of O(n*sum), where n is the length of the sequence and sum is the total sum. Another approach is to use a backtracking algorithm, which has a time complexity of O(2^n). However, for a finite sequence, both of these algorithms should work efficiently.

In terms of the states' numbers, as you mentioned, they do not follow Moore's Law, but we can still optimize the algorithm by considering the fact that the total sum of the numbers in the sequence will always be even (as half of it needs to be an integer). This knowledge can help us in pruning the search space and making the algorithm more efficient.

In conclusion, while there may not be a direct and easy solution to this problem, there are known algorithms that can efficiently solve it. I hope this helps in your further exploration of this problem. Thank you for your inquiry and happy problem-solving!