I was asked this question by a highly-respected political writer and couldn't come up with any convenient way to provide him with an answer. Nor does there appear to be any guidance on Google. So let me pose it to the collective:
How many unique ways are there to acquire at least 270 electoral votes without any excess?
For example, one combination would be to win California, Connecticut, the District of Columbia, Hawaii, Illinois, Maine, Massachusetts, Michigan, Minnesota, New Hampshire, New Jersey, New York, Ohio, Oregon, Pennsylvania, Rhode Island, Vermont, Washington and Wisconsin. That would be equal to 272 electoral votes (not coincidentally, these are the John Kerry states plus Ohio).
Note that there are no excess electoral votes in this combination: if you remove one of the states with three electoral votes, the number falls to 269, which is below the 270-EV cut-off. So winning all of these states plus North Dakota would not qualify, since the candidate has superfluous electoral votes. On the other hand, replacing Vermont with North Dakota would make for a unique combination.
Nothing of monetary value to be provided to the winner, but I will give you a big thank you and shout-out on the front page, and your name will be immortalized in Google and possibly in a national column. I'm hoping that there's some genius out there who can solve this problem in 15 minutes.
p.s. To keep things at least somewhat simple, we probably should not worry about the split electoral votes in Maine and Nebraska.
Tuesday, June 10, 2008
Homework Assignment
-- Nate Silver at 3:29 PM
Labels: electoral math
197 comments
(not in any order)
NV, UT, AZ, ID, MT, WY, CO, NM, TX, LA, AR, MO, IA, KS, NE, SD, ND, NS, TN, KY, IN, OH, WV, VA, NC, SC, GA, FL, AK
Just 83 billion more to go!
Is "at least 13 billion" sufficient?
Someone will be able to do this. It should be pretty easy to write some code to cycle through all the combinations of >270, subtract the minimum value from each one, and keep the ones that remain over 270.
I can probably figure it out, but I know someone will be able to do it much faster than I can. If nobody steps up, I'll give it a shot.
Well, to narrow it down you must have at least one of CA, TX, NY, FL, IL, PA, OH, MI, GA, NJ, NC. All of the others only add up to 267. That gets rid of quite a few of those 83 billion... And no, I don't think there are nearly 13 billion - you must be forgetting the "no extras" requirement. This is some sort of minimum spanning set problem...
If this is still unsolved at around 9 tonight when I get off work, I will go ahead and code it up in a program.
-George Brabazon
Computer science notes:
Initial gut-reaction was that this may be NP-complete. Been a while since I took algorithmic analysis, but iirc the question "Given a set of integers, is there a way to get them to add to a certain number" is NP-complete, and this problem could be reduced to that one (that is, if you could efficiently answer your question, you could do so also for all NP-complete problems).
Not positive after rethinking about it, but if anyone has a good algorithmic idea for it, go for it. My first thought was to use recursion on the "winning" state.
You could find the answer to an NP-complete question, it just won't be efficient ;).
It seems pretty easy. Just hire whoever wrote Obama's leaked February state delegate breakdowns. It appears they were remarkably close to guessing how the primary would break down.
See this article that breaks it down:
http://www.motherjones.com/mojoblog/archives/2008/06/8643_revisiting_the_1.html
This appears to be a modified Knapsack problem.
I'm not good enough to attempt to solve this kind of problem (yet!), so I'll just outline what I think might be a possible solution method and I'll let people smarter than me work on it.
I'd solve multiple knapsack problems with n varying from 270 to, say, 280. Solve each knapsack problem of the form X1 + X2 + X3 + ... + Xk = n. Then, in each solution, find the value of the smallest contribution(s) and label it Xmin. Then check if n - Xmin => 270. If this is the case, remove that solution. If not, you've got yourself one scenario.
That's basically it. Someone better at using Maple/MATLAB/Mathematica/etc. should be able to solve it pretty easily. Here's a list of states with their electoral votes allocation. Copy/paste and Excel can easily sort it out.
Good luck to anyone who tries their hand at that problem.
How about Bush getting 271 in 2000? Is there some reason why that wouldn't count?
ID, MT, WY, UT, CO, AZ, NV, AK, TX, OK, NE, ND, SD, MN, IA, WI, MI, IN, OH, KY, WV, TN, NC, SC, GA, AL, MS, AR, LA, NH all add up to 270. Took 15 seconds on 270towin.com
Hmm, well, there are about 2.25 quadrillion ways for the election to pan out. That means about 1.125 quadrillion ways to win. I won't even attempt to go exact, here, but I'm going to say "a ludicrous number". Trillions and trillions.
Auxiliary question would be what's the largest number of EV's that a candidate could get that would be consistent with the criteria.
Whoever solves this, please provide the distribution of outcomes that satisfy the criteria. Thanks!
Alex, you've got it backwards. For arbitrary sets of numbers, the generalized problem is NP-complete. But for this particular set of numbers, it's not necessarily. Indeed, the answer to your decision problem is "Yes", since people have already posted ways to do it. The answer to the counting problem is somewhat more difficult.
Off hand, the best way looks like dynamic programming. Enumerate the ways to get 1 electoral vote, then 2, etc. But you need to account for the fact that you can't win the same state twice, so each of the ways to get n votes needs to carry along the set of states used to satisfy it; and if the set of solutions is large enough, then this will grow out of control.
There's no way there's trillions and trillions of solutions.
And then are are auxiliary questions such as this: given that CA, IL, and NY all go to Obama, how many ways are there for McCain to beat him by the minimum needed with no extra states.
Maybe this can be programmed into a spreadsheet or game that the users solve.
Many of your are not reading the problem carefully. The stated conditions require coming to exactly 270 EVs. 271 is a no go.
Having one answer is not what the question is about. It is the total number of questions.
judas_priest,
No, he says at least 270.
Anon 4:19:
Your auxillary question is easy:
CA (55), TX (34), NY (31), FL (27), IL (21), PA (21), OH (20), MI (17), VA (13), MA (12), and two of the three worth 15: GA, NC, NJ.
Adds to 281, 11 over.
No J_P, it's OK to go over 270 as long as you do not have any extra states in the combination. See Nate's original illustration. The number of ways to get exactly 270 is just one set of winning combinations that avoid having superfluous states.
Steve--
Hey there, fellow Steve. No way it's trillions and trillions? I dunno, I wouldn't be surprised. If the total number of winning scenarios is over a quadrillion, just one in a thousand meeting the criteria would be a trillion. Maybe one in a thousand *is* over-optimistic, I suppose; how would you estimate it?
This question and the responses -- knapsack problem, dynamic programming -- is jarring my memories of CS101.
Its great, keep it coming!