Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Subsequence that Sums Up to Half the Total Sum

  1. Feb 25, 2013 #1
    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$$.
  2. jcsd
  3. Feb 26, 2013 #2
    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.
  4. Feb 26, 2013 #3
    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.
    New Mexico
    New Jersey
    New York
    Rhode Island
    New Hampshire

    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/ [Broken]
    Last edited by a moderator: May 6, 2017
  5. Feb 26, 2013 #4
    Look up the partition problem. It seems that it can be solved with dynamic programming.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook