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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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/ [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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Subsequence that Sums Up to Half the Total Sum
  1. Fortran Riemann Sum (Replies: 2)

Loading...