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.
6.10.2008
Homework Assignment
@ 4:29 PM
Subscribe to:
Post Comments (Atom)
200 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!
Judas (+others),
To clarify, a candidate does not need to have exactly 270 electoral votes. He just can't have any more votes than is necessary based on the particular combination of states he selects (that is, he can't subtract any states from his combination and still have a winning number).
Since the smallest bundle of electoral votes is 3, all unique combinations of 270, 271 and 272 electoral votes should meet the conditions of the problem. After that, you can start to whittle things down pretty quickly. For example, a 273-EV combination can only include states with 4 electoral votes or more, because if there were any 3-EV states, you could subtract that state and still have a winning combination.
I don't expect this to be a problem that can be solved by a computer (or human) in any reasonable amount of time. It should be on the order of 10^15 or so.
Stephen,
I really don't know for sure, but intuitively it would seem to me that the "without excess" qualification is really going to narrow down the possible solutions. I could be wrong.
Thanks, Stephen!
All kinds of questions could be asked (easy to do, since I can't provide the answer), such as what is the smallest number of states needed that satisfy the criteria? And what is the largest number of states that could combine to satisfy the criteria?
And to minimize costs, the candidate might want to find the minimum number of contiguous states that would satisfy the criteria.
Of course, the shortest combination will be that with the states with more delegates. Once you have it, then you just have to substitute one state in for two or more states out of the count. Then, you go all the way until you reach the longest combination, the one with the states with less delegates accounting at least 270 ones.
It seems pretty computable.
Here's the algorithm I think could work. It's a greedy "bin packing" type of problem.
1) Sort into decreasing weight
2) Add CA to the list
3) Add states until over 270 (print once exceed 270)
4) Remove last item and continue
5) If no more items to add, remove previous item
6) If no more items to remove, move to next highest weight (TX) and start over
7) Once you're at NC as your "root", stop (no combinations of smaller states will work)
Anon and Orlando--
No prob, and yep. 11 and 41, for the record.
Yes, there are 51 states with possible outcomes each (win or lose), so there are 2^51 (approx. 2.25 quadrillion potential outcomes). I simulated 1 million random outcomes, so that each of these 2^51 outcomes are equally likely, and 22,790 met the criteria (sum of the votes >=270, sum - minimum <270), indicating approximately that this criteria would be met about 2.3% of the time. Since this is a binomial experiment, where n=1,000,000 and x=22,790, then p-hat=0.02279 with a 95% confidence interval of (0.02249, 0.02309). Multiply this probability by the 2^51 total possible outcomes and you get an estimated 51.3 trillion unique ways, with a confidence interval of (50.6 trillion - 52.0 trillion). If this isn't precise enough, I can try to rerun the simulation 10 million times, and would therefore have less uncertainty.
Maine, Massachusetts, Connecticut, Vermont, Rhode Island, New York, New Jersey, Pennsylvania, Delaware, Maryland, Washington DC, Virginia, Wisconsin, Minnesota, Iowa, Illinois, Colorado, New Mexico, Nevada, Washington, Oregon, California, and Hawaii.
Adds up to 270 exactly.
Thanks Chris for the correction. Rethinking the problem you're exactly right--dynamic programming looks like the way to go here.
So, basic formulation of a dynamic programming algorithm... (I started writing the solution and then ran into your set-keeping problem. Two steps ahead of me!!)
OPT[n] = number of ways that you can get to N electoral votes with no overflow.
OPT[n < 3] = 0
OPT[3] = 8, eight sets of {3-EV states}
OPT[n] = {
x = 0
foreach(state S with EV Sv){
x = x + # of sets in OPT[n - Sv] where S does not appear in the set
}
}, all such created sets with S added in.
It's a lot of bookkeeping.
I stand corrected. Trillions, it is.
Brian: I assume by trillion you mean 10^12. So 5*10^13? This is in the ballpark of what I expected. My guess (about 10^15) was based on the fact that (50 choose 25) is about 10^14. I guess big states like California and Texas reduce the number of combinations.
It seems to me that the answer to this question may have use in a math or computer science class, but has zero practical utility and thus is useless for a journalist.
My 2 cents.
Yes, my final confidence interval was (5.064,5.199) x 10^13
I think we still haven't restated the problem correctly. This seems closer:
Define a minimal winning set as a subset S of all 51 states, where:
• Σ EV(s) >= 270, and
• Σ EV(s) - min(EV(s)) < 270
How many MWSs are there?
Final comment, you would terminate the algorithm at N = 272 and then count OPT[270] + OPT[271] + OPT[272] as your solution.
the question can be answered by the owl perched atop the fence post.
I get everything wrong the first time and can't edit my comments. The algorithm will only work if you're forced to include a 3 EV state. If you build your 270 with bigger states, you're much higher than OPT[270] BUT the algorithm is operating like it wants OPT[270 + your smallest state] as the "no overflow" level instead of 270. Back to the drawing (tweaking?) board...
Brian, you get points for most creative answer. Running a simulation and extrapolating seems like the best, fastest answer. I'm curious to see who will come up with the answer for the population (instead of just the answer for the sample) to see how close you are.
Great question.... wish I knew a clever way to solve it besides writing a very inefficient program to check all possibilities. I'll leave that to others. :)
Here's an easy one so the rest of us can have something to do.... I think I know the answers. What is the smallest number of states you can win and win the presidency outright? How many distinct choices of states are there giving this result?
Similarly, what is the smallest number of states you can get to reach an electoral tie? How many combinations give you that result?
I'm pretty sure this is not a polynomial time problem, but I'm too lazy to write a proof right now. I think Brian's approach is correct unless you have computers that have more atoms than appear in observable universe.
I don't have an answer to this question, but in attempting to answer it I stumbled upon a crazy - yet quite possible - scenario: a 269-269 tie. (Sorry if this has already been discussed before.) It would happen in the following scenario:
Obama: WA, OR, CA, HI, NV, CO, MN, IA, WI, IL, MI, DC, MD, DE, PA, NJ, NY, CT, MA, VT, ME.
McCain: AK, ID, UT, AZ, MT, WY, NM, ND, SD, NE, KS, OK, TX, MO, AR, LA, IN, KY, TN, MS, AL, GA, FL, SC, NC, VA, WV, OH, NH
No splits in NE or ME.
According to 270towin.com (sorry, I haven't taken the time to check the Constitution), if the electoral college ends in a tie, the House votes on the President, with each state's delegation getting one vote. In the above scenario, Obama wins 20 states plus DC; so if each state delegation went with its state popular vote, McCain would win. Meanwhile, the Senate (controlled by the Dems) would pick the VP.
Who's up for another election disaster? (Not me.)
I coded a quick hack that gave me 51199463116367 which seems to be in line with brian's estimate.
It sure seems like this is a merely academic problem. If it was meant to be even remotely useful politically then it would have to take into account which states could actually be won. For example NY/CA/MA will be Dem no matter what.... so that would greatly reduce the number of combinations and the effort. Especially if you also rule out OK, ID, WY, NB, etc.
Some states will vote the way they vote no matter what happens really, and if they didn't then obviously you wouldn't end with 270-272 votes, heh.
So it depends, if a theoretical answer is wanted then fine... but if a practical answer is wanted then it needs to be restated.
I am pretty certain that like any NP problem, there's no particularly fast way to calculate this. The fact is that in order to determine if a set of states meets the MWS definition (an accurate appraisal I think), you must first determine the sum for each set, which requires by necessity a computation (or a built up running computation) for every set. There may be a few tricks to speed it up a little, but it will still take a very large amount of computation regardless.
That said, here is my completely unoptimized Python code which has been running for about 30 minutes without a hit, although I really doubt this is anywhere near optimal:
n = 0
nsets = 10
maxsets = 30
set = []
for i in range(0,maxsets):
\for x in xuniqueCombinations(elec.keys(), i):
\\sum = 0
\\min = 0
\\for j in x:
\\\if elec[j] > min:
\\\\min = elec[j]
\\\sum += elec[j]
\\\if(sum - min) < 270 & sum > 270:
\\\\print "Minimum"
\\\\print x
\\\\print sum
\\\\n += 1
\\\if n == nsets:
\\\\break
\\if n == nsets:
\\\break
Well, I coded something up and got 243 unique minimum combinations. Let me know if there's a problem.
They are:
NC NJ GA MI OH PA IL FL NY TX CA Sum: 271
MA VA NJ GA MI OH PA IL FL NY TX CA Sum: 281
IN VA NJ GA MI OH PA IL FL NY TX CA Sum: 280
MO VA NJ GA MI OH PA IL FL NY TX CA Sum: 280
TN VA NJ GA MI OH PA IL FL NY TX CA Sum: 280
WA VA NJ GA MI OH PA IL FL NY TX CA Sum: 280
AZ VA NJ GA MI OH PA IL FL NY TX CA Sum: 279
MD VA NJ GA MI OH PA IL FL NY TX CA Sum: 279
MN VA NJ GA MI OH PA IL FL NY TX CA Sum: 279
WI VA NJ GA MI OH PA IL FL NY TX CA Sum: 279
AL VA NJ GA MI OH PA IL FL NY TX CA Sum: 278
CO VA NJ GA MI OH PA IL FL NY TX CA Sum: 278
LA VA NJ GA MI OH PA IL FL NY TX CA Sum: 278
KY VA NJ GA MI OH PA IL FL NY TX CA Sum: 277
SC VA NJ GA MI OH PA IL FL NY TX CA Sum: 277
CT VA NJ GA MI OH PA IL FL NY TX CA Sum: 276
IA VA NJ GA MI OH PA IL FL NY TX CA Sum: 276
OK VA NJ GA MI OH PA IL FL NY TX CA Sum: 276
OR VA NJ GA MI OH PA IL FL NY TX CA Sum: 276
AK VA NJ GA MI OH PA IL FL NY TX CA Sum: 275
KS VA NJ GA MI OH PA IL FL NY TX CA Sum: 275
MI VA NJ GA MI OH PA IL FL NY TX CA Sum: 275
NE VA NJ GA MI OH PA IL FL NY TX CA Sum: 274
NV VA NJ GA MI OH PA IL FL NY TX CA Sum: 274
NM VA NJ GA MI OH PA IL FL NY TX CA Sum: 274
UT VA NJ GA MI OH PA IL FL NY TX CA Sum: 274
WV VA NJ GA MI OH PA IL FL NY TX CA Sum: 274
HI VA NJ GA MI OH PA IL FL NY TX CA Sum: 273
ID VA NJ GA MI OH PA IL FL NY TX CA Sum: 273
MN VA NJ GA MI OH PA IL FL NY TX CA Sum: 273
NH VA NJ GA MI OH PA IL FL NY TX CA Sum: 273
RI VA NJ GA MI OH PA IL FL NY TX CA Sum: 273
AK VA NJ GA MI OH PA IL FL NY TX CA Sum: 272
DE VA NJ GA MI OH PA IL FL NY TX CA Sum: 272
DC VA NJ GA MI OH PA IL FL NY TX CA Sum: 272
MT VA NJ GA MI OH PA IL FL NY TX CA Sum: 272
ND VA NJ GA MI OH PA IL FL NY TX CA Sum: 272
SD VA NJ GA MI OH PA IL FL NY TX CA Sum: 272
VT VA NJ GA MI OH PA IL FL NY TX CA Sum: 272
WY VA NJ GA MI OH PA IL FL NY TX CA Sum: 272
TN MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 274
WA MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 274
AZ MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 273
MD MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 273
MN MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 273
WI MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 273
AL MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 272
CO MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 272
LA MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 272
KY MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 271
SC MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 271
CT MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 270
IA MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 270
OK MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 270
OR MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 270
KS AK MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 275
MI AK MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 275
NE AK MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 274
NV AK MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 274
NM AK MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 274
UT AK MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 274
WV AK MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 274
HI AK MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 273
ID AK MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 273
MN AK MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 273
NH AK MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 273
RI AK MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 273
AK AK MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 272
DE AK MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 272
DC AK MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 272
MT AK MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 272
ND AK MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 272
SD AK MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 272
VT AK MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 272
WY AK MO IN MA VA NC NJ GA MI OH PA IL FL NY TX Sum: 272
MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 271
MN AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 271
WI AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 271
AL AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 270
CO AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 270
LA AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 270
SC KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 277
CT KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 276
IA KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 276
OK KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 276
OR KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 276
AK KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 275
KS KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 275
MI KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 275
NE KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 274
NV KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 274
NM KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 274
UT KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 274
WV KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 274
HI KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 273
ID KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 273
MN KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 273
NH KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 273
RI KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 273
AK KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 272
DE KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 272
DC KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 272
MT KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 272
ND KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 272
SD KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 272
VT KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 272
WY KY AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL NY Sum: 272
CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 278
LA AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 278
KY AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 277
SC AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 277
CT AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 276
IA AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 276
OK AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 276
OR AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 276
AK AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 275
KS AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 275
MI AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 275
NE AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 274
NV AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 274
NM AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 274
UT AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 274
WV AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 274
HI AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 273
ID AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 273
MN AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 273
NH AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 273
RI AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 273
AK AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 272
DE AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 272
DC AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 272
MT AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 272
ND AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 272
SD AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 272
VT AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 272
WY AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL FL Sum: 272
SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 276
CT KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 275
IA KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 275
OK KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 275
OR KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 275
AK KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 274
KS KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 274
MI KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 274
NE KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 273
NV KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 273
NM KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 273
UT KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 273
WV KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 273
HI KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 272
ID KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 272
MN KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 272
NH KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 272
RI KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 272
AK KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 271
DE KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 271
DC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 271
MT KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 271
ND KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 271
SD KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 271
VT KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 271
WY KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA IL Sum: 271
OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA Sum: 276
OR IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA Sum: 276
AK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA Sum: 275
KS IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA Sum: 275
MI IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA Sum: 275
NE IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA Sum: 274
NV IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA Sum: 274
NM IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA Sum: 274
UT IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA Sum: 274
WV IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA Sum: 274
HI IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA Sum: 273
ID IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA Sum: 273
MN IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA Sum: 273
NH IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA Sum: 273
RI IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA Sum: 273
AK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA Sum: 272
DE IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA Sum: 272
DC IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA Sum: 272
MT IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA Sum: 272
ND IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA Sum: 272
SD IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA Sum: 272
VT IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA Sum: 272
WY IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH PA Sum: 272
KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH Sum: 274
MI AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH Sum: 274
NE AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH Sum: 273
NV AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH Sum: 273
NM AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH Sum: 273
UT AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH Sum: 273
WV AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH Sum: 273
HI AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH Sum: 272
ID AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH Sum: 272
MN AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH Sum: 272
NH AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH Sum: 272
RI AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH Sum: 272
AK AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH Sum: 271
DE AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH Sum: 271
DC AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH Sum: 271
MT AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH Sum: 271
ND AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH Sum: 271
SD AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH Sum: 271
VT AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH Sum: 271
WY AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI OH Sum: 271
NV NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI Sum: 270
NM NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI Sum: 270
UT NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI Sum: 270
WV NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI Sum: 270
ID HI NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI Sum: 273
MN HI NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI Sum: 273
NH HI NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI Sum: 273
RI HI NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI Sum: 273
AK HI NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI Sum: 272
DE HI NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI Sum: 272
DC HI NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI Sum: 272
MT HI NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI Sum: 272
ND HI NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI Sum: 272
SD HI NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI Sum: 272
VT HI NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI Sum: 272
WY HI NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA MI Sum: 272
HI WV UT NM NV NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA Sum: 272
ID WV UT NM NV NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA Sum: 272
MN WV UT NM NV NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA Sum: 272
NH WV UT NM NV NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA Sum: 272
RI WV UT NM NV NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA Sum: 272
AK WV UT NM NV NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA Sum: 271
DE WV UT NM NV NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA Sum: 271
DC WV UT NM NV NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA Sum: 271
MT WV UT NM NV NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA Sum: 271
ND WV UT NM NV NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA Sum: 271
SD WV UT NM NV NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA Sum: 271
VT WV UT NM NV NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA Sum: 271
WY WV UT NM NV NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ GA Sum: 271
RI NH MN ID HI WV UT NM NV NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ Sum: 273
AK NH MN ID HI WV UT NM NV NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ Sum: 272
DE NH MN ID HI WV UT NM NV NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ Sum: 272
DC NH MN ID HI WV UT NM NV NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ Sum: 272
MT NH MN ID HI WV UT NM NV NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ Sum: 272
ND NH MN ID HI WV UT NM NV NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ Sum: 272
SD NH MN ID HI WV UT NM NV NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ Sum: 272
VT NH MN ID HI WV UT NM NV NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ Sum: 272
WY NH MN ID HI WV UT NM NV NE MI KS AK OR OK IA CT SC KY LA CO AL WI MN MD AZ WA TN MO IN MA VA NC NJ Sum: 272
Matches: 243
To the Anon worried about a tie,
Yes, that configuration is well-known and well within the bounds of possibility. But there's no reason to think the House delegations would vote based on the popular votes in their own states. It's much more likely they'll vote based on whichever party dominates their delegation. The one-vote-per-state thing muddies the waters a little, but considering where the House will likely be in January, a 269-269 tie is much more likely to be a victory for Obama.
51,199,463,116,367, which matches nicely with Brian's simulation-based estimate. This is about 2.27% of all the possible combinations.
50,939,354,221,562 of these -- over 99% -- involve at least one 3-electoral-vote jurisdiction. This isn't surprising -- if you pick a set of states at random it's quite likely that it'll include at least one of the 3-EV states, since there are eight of them!
Dynamic programming would work, but I'm a mathematician, not a computer scientist. So my method was as follows: the polynomial (1+x^55)*(1+x^34)*(1+x^31)*(1+x^27)*(1+x^21)^2*(1+x^20)*(1+x^17)*(1+x^15)^3*(1+x^13)*(1+x^12)*(1+x^11)^4*(1+x^10)^4*(1+x^9)^3*(1+x^8)^2*(1+x^7)^4*(1+x^6)^3*(1+x^5)^5*(1+x^4)^5*((1+x^3)^8-1)
has as its coefficient of x^n the number of sets of states which add up to n electoral votes, which includes at least one 3-EV state. This basically follows from the process of multiplication. It's easy to get a computer algebra system to expand this (I use Maple) and extract the coefficients of x^270, x^271, and x^272; adding these together gives the total number of ways to get 270, 271, or 272 electoral votes using at least one 3-EV state, which is the smaller of the two numbers above.
Removing the ((1+x^3)^8-1) factor, and replacing the second-to-last factor with (1+x^4)^5-1, then allows us to consider the states which have four or more electoral votes. We take that polynomial and extract the coefficients of x^270, x^271, x^272, and x^273 -- adding those together gives the total number of ways to get 270, 271, 272, or 273 electoral votes using no 3-EV states and at least one 4-EV state.
Repeat for the cases where the smallest state is a 5-EV state, a 6-EV state, ..., a 15-EV state, add those up, and that gives the answer.
I got 292 possibles in my count - i'll check my code
debbie
I concur with andras, interestingly there are 17,057,441,245,652 combination that lead to a draw.
Wow,
This is kinda too much. Well, this is what I found out.
To get exactly 270 EV,
- the minimum number of states to win is 12 states (there are already 237 ways to do this)
- the maximum number of states to win is 40 states (there are 3 ways to do this)
Well, my idea is to do combinatorics. But it's too inefficient...
"51 choose 12" --> 237 ways to get exactly 270
"51 choose 40" --> 3 ways to get exactly 270
The people saying that the number is in the trillions are right. The total number of combinations of states is 2^51 or about two quadrillion. (each state/DC is either in or out.) In each of these cases, the sum of electoral votes is an integer from 0 to 538. Even if all sums were equally numerous (sums near 269 are actually MORE numerous than sums near the endpoints), about one in 200 or 10 trillion would have 270 271 or 272 electoral votes.
To further estimate, we can examine the variance of these scenarios, (the sum of the squares of each states EV number divided by 4), and model based on a bell curve type distribution.
Anyhow, the std dev. ends up at around 50. The peak probability density is therefore 1/(50sqrt(2*pi) =~ .008
The scenarios not containing a 3EV state are less than .4% and may be ignored in our estimate. Thus,
2.5% of all scenarios are expected to have 270, 271 or 272 EVs.
Thus I estimate there are 50 trillion ways to solve this problem. I'm not a big coding fan, but feel free to check my work with a monte carlo simulation.
Actually, a 269-269 tie is possible.
Obama wins WA, OR, CA, CO, NM, MI, IA, WI, IL, PA, NY, MD DE NJ DC, CT RI MA, ME, VT (no split) - all states he is currently wining
He also wins MI (very very likely)
That's 269.
McCain wins everything else (he is leading in all of these states).
Essentially add CO and NM and IA and take away NH. Very very reasonable.
A quick follow-up.
If you scrub the names off the states you can find the individual ways of combining the numbers to get a MWS. Each combination gets multiplied by the number of permutations of states with the same EVs to determine its contribution. [e.g. if a combination requires 4 of the 8 3-EV states, there are 70 ways to assign those four 3-EV states.]
However, there are nearly six billion of those! Smaller than the aforementioned 2.25 quadrillion total possibilities, but still daunting.
The normal approximation for 538 coinflips gives a 10.14% chance of getting between 270 and 272 heads. That seems like an upper bound. Of 0.225 quadrillion. (Yikes.)
Very impressive, Isabel. I took a course on that touched on that kind of mathematics once, but obviously don't know it well enough to come up with something that elegant. Cool.
Oliver,
Thanks for the response. Are there a number of states (ten or more) whose House delegations are majority-Dem, yet would vote for McCain in the general? Maybe OH, NM...but are there others?
-RFC (Anon @ 5:11)
So, we know the answer is somewhere between 243 and 50 trillion.
Alex,
well, I should hope I'm able to do this -- I've taken more courses in combinatorics than I care to count.
I believe Isabel gave the exact number.
> I've taken more courses in combinatorics than I care to count.
Heh. Is this a standard joke among combinatorists? It's better than most of the standard math jokes I hear, you know about Abelian grapes and all.
This is a generalized version of the "subset sum" problem in computer science and it is NP-hard, which in English means that it's extremely difficult to figure out the answer exactly.
http://en.wikipedia.org/wiki/Subset_sum
Looks like this is answered. I went to estimate how tough a brute force computation would be.
While this can be *hugely* pared down, I asked simply how many possible combinations of states (plus DC) could a candidate win. That's:
Sum(i=0..51) [ C(51,i) ]
which is 2,251,799,813,685,248.
Oh well. Can't beat an exact solution. I'm still proud of myself for getting within a couple percent of the right answer using nothing more than Windows calculator.
To be clear, the goal is not an exact number of EV's. To put it as mathematically as I can:
Each possible solution must have ≥270 electoral votes.
No subset of any possible solution should have ≥270 electoral votes.
anon 18:37,
It's not a standard joke among combinatorists (combinatorialists? combinatoricists?) but it probably should be. I'll see what I can do to popularize it.
Isabel, great solution! Now that you explain it, it's very straightforward.
RFC, check this out:
http://en.wikipedia.org/wiki/Image:110th_US_Congress_House_of_Reps_13_May_08.png
Democrats are the majority in more than half of the states in the House. States like AR, MS, TN, IN, WV, NC and the Dakotas voted for Bush but have more Democrats in the House, while I think only MI and DE voted for Kerry but have more House Republicans.
So Dems already dominate this calculus, and after November, it would not be surprising at all for quite a few more of those states to flip Dem - and it's the new Congress, not the old one, that decides the ties.
Is andras the same person as Isabel? Andras posted the same answer about 7 minutes prior, but gave no explanation.
It is actually not 2^51. Nebraska counts four times (3CDs plus overall award) and Maine counts three times (2CDs plus overall award). That makes 2^56, or 32 times harder to solve via brute force.
In terms of the tie issue, it's worth suggesting that a bunch of the lamer Democrats (the two white Democrats in Mississippi, for instance, the sole Democratic congresspeople in North and South Dakota) would lame out and vote for McCain - I doubt that Taylor and Childers will even endorse Obama.
This could very easily cost Obama the election in the House, although I think they could be nudged into doing the right thing, assuming Obama won the national popular vote.
If McCain wins the national popular vote, I find it very unlikely that Herseth Sandlin, Pomeroy, Taylor, and Childers would vote for Obama, lowering by at least three the number of states Democrats have a majority in.
I've got a program running right now, and it has already gotten over 1,000,000 different possibilities, all of which so far include CA, TX, NY, FL, IL, PA, OH, and MI.
Also,
http://www.fivethirtyeight.com/2008/05/like-kissing-your-sister.html
As was pointed out above, the answer is no more that 2^51 =
2,251,799,813,685,248
If you ignore ties of 269-269 then the answer including excess will be about half the above. Not including excess is the difficult part.
I now have a program running on a old laptop doing the actual counting. The answer is still far from finished, but it is at least
2,593,142,010,890
I doubt I will let the program finish.
What's with the display of comments? The beginning ones are not displayed.
Isabel-
Would it be hard to modify your method to consider Maine and Nebraska's EV allocation? I suppose all you would have to do would be to consider each CD a state of 1 EV.
Aaron,
it's not quite that simple. If a candidate wins both Maine districts, then they must win Maine; similarly if they win all three Nebraska districts they must win Nebraska.
But it wouldn't be too hard, either. I'll give it a shot.
HI, Wash, OR, CAL, MINN, IA, WIS, MICH, MASS, MAINE, NH, RI, VT, ILL, IND, PA, MD, DC, DEL, NJ, NY, CT
NE can have any value from 0-5:
0 = lose all districts, lose state
1 = win one district, lose state
2 = win two districts, lose state
3 = win one district, win state
4 = win two districts, win state
5 = win all districts, win state
ME can assume any value but 2:
0 = lose both districts
1 = split districts, lose state
3 = split districts, win state
4 = win both districts
Come to think of it, the problem isn't really well-defined if we take into account Maine and Nebraska. Is, say, a situation with 271 EV including two of the three Nebraska CDs and the state something that should be included in the count? Removing any state takes it under 270, but removing one of the two Nebraska CDs doesn't.
That is absolutely beautiful Isabel.
Strangely, I get 51199463116364 -- three fewer than your result.
If you want to do it for 269 -- a situation where any single state flipping would take it from a win to a loss *or tie*, the value I get is 51224779811077.
Mathematica code here.
int i, j, states[51] = {55,34,31,27,21,21,20,17,15,15,15,13,12,11,11,11,11,10,10,10,10,9,9,9,8,8,7,7,7,7,6,6,6,5,5,5,5,5,4,4,4,4,4,3,3,3,3,3,3,3,3};
long long total = 0, poss[539] = {1};
for( i=0; i<51; i++)
for( j = 269 + states[i]; j >= states[i]; j--)
poss[j] += poss[j - states[i]];
for( i=270; i<539; i++)
total += poss[i];
cout << "Number over 269: " << total << endl;
Props to isobel.
Propose canonical form for joke: "There are more ways to learn combinatorics than you can count".
Isabel: The best way I can think of to make the problem well defined is to consider scenarios where removing votes (and not adding any) until at least one EV flips will always change the outcome. Thus a 271 vote scenario with 4 of NE's EV's would be minimal iff the margin in the losing district was larger than the margins in each of the winning districts.
I say count any EV scenario that can be minimal by the above definition.
Isabel, nice work
flip, my mathematica code agrees with Isabel. In detail
Smallest state | Combinations
3 | 50,939,354,221,562
4 | 250,611,676,072
5 | 9,182,493,852
6 | 275,274,974
7 | 37,312,075
8 | 1,663,868
9 | 433,036
10 | 39,884
11 | 1,036
12 | 7
13 | 0
15 | 1
And my dynamic programming solution in Haskell is perhaps not so hopeless: it is up to at least 42,851,039,747,613 (assuming my program is correct...)
Gah -- Isabel's answer is of course correct. My program didn't pick the three cases where there was exactly one outcome.
There are 50 states, plus DC and 5 more variations due to split EV's in NE and ME. For the intent of this problem, we can treat that as 56 'states'.
Using that figure, the maximum number of 'states' that can be used to reach 270 votes is 42.
Since each is a binary choice (red or blue), we can treat that as a binary number. 2^42 equals a maximum of approximately 4.4 trillion unique solutions.
Since, obviously, the great majority of those solutions will be composed of much shorter strings than 42 digits, my half-assed guess is that the actual number of unique solutions will be in the vicinity of the square root of that number - roughly 2 million (or 2^21), with a big-ass margin of error.
Don't know if that helps anyone. I just thought it would be useful to point out that the people saying there would be 'trillions and trillions' of solutions are way off base - by orders and orders of binary magnitude.
.
By the way, when I say 'big-ass margin of error', I mean a decimal order of magnitude.
That puts the number of unique solutions somewhere in the range of hundreds of thousands to the low tens of millions.
.
JGabriel: Since, obviously, the great majority of those solutions will be composed of much shorter strings than 42 digits...
Sorry, that's badly and misleadingly worded.
A better way of putting it is that, since we know a lot of those strings will add up to way more or way less than 270 votes, the number of actual solutions... da da da, continuing with the above analysis as is.
.
Here's a solution in Haskell:
tabulate n xs = zipWith (+) xs (replicate n 0 ++ xs)
count k = (foldr tabulate (1 : repeat 0) (filter (> k) evs)) !! (270 + k)
result :: Integer
result = sum $ map count [0..11]
evs = [9,3,10,6,55,9,7,3,3,27,15,4,4,
21,11,7,6,8,9,4,10,12,17,10,6,11,3,
5,5,4,15,5,31,15,3,20,7,7,21,4,8,3,
11,34,5,3,13,11,5,10,3]
The answer it gives is 51199463116367.
JGabriel. You're representing solutions as a list of states, not as a binary string. Your upper bound is therefore 56^42, not 2^42. 56^52 is a good bit larger than a few trillion.
Isabel gives the correct number (ignoring congressional district splits).
Anonymous@4:37PM:
I'm pretty confident that the minimum number of contiguous states a candidate would need to win is 14.
Basically, you find the most efficient paths to connect every state with more than 20 EVs and then throw in one other state. Though, you can do it without Illinois, and if you don't count DC as a state, there are a number of ways to get it in 14 without Florida (there are no ways to minimize the amount without NY, PA, TX or CA, and I don't think you can do it without Ohio).
Some of the maps remind me a little of Cliton's primary map, actually. You can construct a minimal contiguous winning map out of only states won by Hillary Clinton and Georgia.
JGabriel: "Using that figure, the maximum number of 'states' that can be used to reach 270 votes is 42."
Fuck. I sure as hell hope this isn't what Douglas Adams meant by the answer to the meaning of life, the universe, and everything.
.
JGabriel - you're wrong. You're assuming the 42 states used to get 270 are fixed, and they're not - they can still be chosen from the entire set of 51, and thus cannot be represented as a 42-bit string. Several people have already found the correct answer (51,199,463,116,367) backed up with dynamic programming (both Haskell and C++ solutions are given) and combinatorics.
To summarize: Brian got the first reasonable approximation, Andras got the solution first, Isabel gave the first explanation for a mathematical solution, Anonymous gave some clever C++ code for a dynamic programming solution, and Eric gave a very concise Haskell implementation. The problem is solved, guys. Unless you have a more elegant solution, or are exploring an interesting side problem (how to deal with ME and NE, for example) - nothing more to see or say here :-P
Here's my php. It has a precision issue of 2 digits but comes to the same results basically as everyone else:
$ev = array(12,7,4,4,4,3,31,15,10,3,3,27,15,15,13,8,34,9,9,6,11,11,8,7,6,5,21,20,17,11,21,10,10,7,6,5,3,3,10,9,5,5,5,4,3,3,3,55,11,7,4);
rsort($ev);
$bucket = array();
for($i=0;$i<=538;$i++)
{
$bucket[$i]=0;
}
$bucket[0]=1;
$oldval = 0;
$total_combos = 0;
foreach($ev as $ind => $val)
{
if($oldval != $val)
for($i=270+$val;$i<(270+$oldval);$i++)
if($bucket[$i]>0)
$total_combos+=$bucket[$i];
$bucket2 = $bucket;
for($i=0;$i<=538;$i++)
{
$bucket2[$i+$val]+=$bucket[$i];
}
$bucket = $bucket2;
$oldval = $val;
}
for($i=270;$i<273;$i++)
if($bucket[$i]>0)
$total_combos+=$bucket[$i];
echo $total_combos . " total combinations.";
Hey nate,
I need your help promoting an idea.
I’m calling it operation Convention chaos, or using Ron Paul’s mini-convention during the Republican convention to split the Republicans.
my link to the idea is here:
http://outtheotherear.wordpress.com/operation-convention-chaos/
If you like the idea, please repost on your blog and ask others to do so as well.
And by basically everyone else, I mean 51199463116400 (rounded), not the wrong answers. :-) I think Isabel gets the points for most elegant solution.
Anon @ 7:05: "You're representing solutions as a list of states, not as a binary string. Your upper bound is therefore 56^42, not 2^42. 56^52 is a good bit larger than a few trillion."
Sorry, Anon, you're wrong. Solutions are a list of states and that list can be treated as a binary number for determining the number of paths that lead to the proper solution:
CA: On = +55
TX: Off = +0
NY: On = +31
FL: Off = +0
PA: On = +21
And so on.
The path to the solution is a variable of 56 digits (i.e., states) in length, each variable representing a set number of EV votes, that can be flipped either off or on.
The solution itself is how many of the unique solutions (from a string of 56 0's to a string of 56 1's), will yield an answer where the associated EV's with each digit (state) totals >269 but no greater than 269 + the smallest state's associated EV.
Since every solution with greater than 42 digits turned on leads to excess states, we can say that the maximum number of solutions is 2^42, and work down from there.
.
Somewhat more interesting as an exercise in playing around with 270towin.com is to try to find solutions with NO contiguous states. I've only found non-contiguous solutions which involve winning NE-02 and then hoping congress chooses you in the tie-break. (Or cheating and winning both DC and VA.) I don't know if it's possible to do better.
JGabriel
To see why your upper bound of 2^42 is wrong: Do the same analysis with 5 EV instead of 269. (Ignore delegate splitting)
At most 2 states are required to go over. -but there are significantly more than 2^2 = 4 combinations.
The number of binary strings with a given Hamming weight is not necessarily the same as the number of such strings with a given number of bits.
Mad props for Haskell!! I *love* Haskell. The fact that someone came up with a program with about five or six executable lines of code that gives the answer to this *instantaneously* is a thing to behold :-)
Yitz: "JGabriel - you're wrong. You're assuming the 42 states used to get 270 are fixed, and they're not..."
Christ, I think you're right. I understand where my error is now - the way I was envisioning the problem, the states are fixed - which is a valid approach - but once you make that assumption, you can't arbitrarily push them around to create shorter strings. The solution set is still in a 56 digit space, not 42.
I get it now. Thanks, yitz.
.
(And in the grand tradition of Haskell, I have no idea exactly what the #@$%! it's doing :-) )
Great fun, and Isabel obviously gets the gold star and pudding cup.
But I think the results would be more interesting if they narrowed into a range that's more plausible. For example, no outcome in which one candidate wins both DC and Utah but not Ohio is politically plausible.
I like the idea of running a Monte Carlo simulation (like Darryl's at Hominid Views) based on the actual probability of winning a state (based on polls, or 538's more in-depth regression) 100,000 times and tracking the unique state combinations that show up. Anything that doesn't come up in that 100,000 rolls isn't going to come up in the election (at least, if that election were held today).
It may be more interesting to see the number of solution sets that each state is a member of.
Isabel: "If a candidate wins both Maine districts, then they must win Maine..."
Actually, Isabel, I think you can ignore that complication. For instance, assume that both CD's have equal population, and that there are four candidates: R, D, L, and G.
CD-1
R=34
D=33
L=30
G= 3
CD-2
R=30
D=33
L=34
G= 3
R wins CD-1, L wins CD-2. G wins nothing. But D wins the state's popular vote with 33% vs. 32% each for the R & L candidates.
So winning the popular vote without winning a CD is a possible, if vanishingly unlikely, scenario in a split CD scenario with more candidates than there are CD's.
Does that make the problem simpler?
.
Okay, I'll shut up now. I just realized that response does nothing to address the issue of treating the popular bvote separately from the CD's in some situations, but necessarily combining them in others.
Just forget I said anything, while I go slink to a corner in embarrassment.
.
Dean: It may be more interesting to see the number of solution sets that each state is a member of.
I think you'll find these numbers to be disappointingly close to half of the total.
California, Oregon, Washington, Missouri, Iowa, Illinois, Minnesota, Wisconsin, Michigan, District of Columbia, Maryland, Delaware, New Jersey, Pennsylvania, New York, Connecticut, Rhode Island, Massachusetts, Vermont, New Hampshire, Maine = 270
Oops, add Hawaii to that list (it still adds up to 270)... By the way, I think my solution to the problem is the most likely of all the solutions.
Just a real quick number crunch: If we assume that all states which are >= 90% for a candidate go to that candidate, then there are 170,500 possible combinations for Obama and 140,496 for McCain.
Erik,
I think I can get to 270 non-contiguously (though I do need to win the congressional district in Nebraska.)
AK, HI, WA, CA, MT, UT, MN, KS, TX, IL, MS, OH, NY, RI, ME, MD, NC, FL (and the lincoln congressional district of nebraska).
Re: Least amount of contiguous states needed.
It does appear to be 14 (CA, AZ, NM, TX, OK, MO, TN, GA, FL, IL, IN, OH, PA, NY for 279 EV). With 13 states, the most I've gotten is 258 (CA, AZ NM, TX, OK, MO, IL, IN, MI, OH, PA, NY, NJ), though another 4 more are possible if you count AZ-CO as contiguous.
Poblano, I read the article about you in Newsweek. Oh my god!! you are so young and cute. It's very nice knowing at least how you look. Nice job Poblano, keep it up!
Of course, as usual, people are asking the wrong QUESTION.
Who cares that there are 51,199,463,116,367 ways to get 270? What's MUCH more interesting is the percentage of line-ups that lead to 270. Working with the 56 states situation situation
51,199,463,116,367/2^56 = 0.0007105352850029655?
That's a 0.07% chance of this happening, assuming each outcome is equally likely.
Which it's not... but that's another problem. :-D
WA, OR, CA, IA, WI, IL, MI, NC, VA, PA, NY, CT, MA, VT, and ME.
Of course, this is just an academic exercise, considering how unlikely it it is that, as an example, DC votes a different way then NY. But 270 it is, on the dot. The losing side gets 268 in a squeaker.
I ran a simulation in which I ran through the states in decreasing order of Obama win %, stopping when I had 270 EV or ran out of states (signifying a McCain win or tie).
Obama won 54020, with 28147 distinct combinations of states. Most of these combinations only occurred once, of course, there are MANY unlikely combinations. The most likely was DC,VT,HI,IL,CA,NY,WA,MD,RI,OR,ME,DE,MN,MA,NJ,CT,IA,PA,WI,CO,NM,OH i.e. winning every state up to Ohio, which occurred 1968 times.
There were 1405 ties, with 1282 combinations. The most likely was DC,VT,HI,IL,CA,NY,WA,MD,RI,OR,ME,DE,MN,MA,NJ,CT,IA,PA,WI,CO,NM,MI with 16 occurences.
It would be interesting to see a CDF of the probablities of each set of MWSs.( One can think of a number of ways of estimating the probabilities.)
One could then see what jump in success gives the largest increase in possible number of MWS scenarios. It's bound to be non-linear
@Dean: This is the Banzhaf Power Index, a measure of the percentage of times when a state is in position of actually swing a result.
You can find an online calculator in http://cow.math.temple.edu/~cow/bpi.html
I'm not a mathematician or a computer power geek, so I hope I can be forgiven for stating my point in layman's terms:
There might be 2 billion solutions, but you need to screen out the ones that merely rearrange the same list of states.
Charles, these were combinations, not permutations. So there are no order effects.
In English, please?
The real issue is not how well Obama or McCain might do in the closely divided battleground states, but that we shouldn't have battleground states and spectator states in the first place. Every vote in every state should be politically relevant in a presidential election. And, every vote should be equal. We should have a national popular vote for President in which the White House goes to the candidate who gets the most popular votes in all 50 states.
The National Popular Vote bill would guarantee the Presidency to the candidate who receives the most popular votes in all 50 states (and DC). The bill would take effect only when enacted, in identical form, by states possessing a majority of the electoral votes—that is, enough electoral votes to elect a President (270 of 538). When the bill comes into effect, all the electoral votes from those states would be awarded to the presidential candidate who receives the most popular votes in all 50 states (and DC).
The major shortcoming of the current system of electing the President is that presidential candidates have no reason to poll, visit, advertise, organize, campaign, or worry about the voter concerns in states where they are safely ahead or hopelessly behind. The reason for this is the winner-take-all rule which awards all of a state's electoral votes to the candidate who gets the most votes in each separate state. Because of this rule, candidates concentrate their attention on a handful of closely divided "battleground" states. Two-thirds of the visits and money are focused in just six states; 88% on 9 states, and 99% of the money goes to just 16 states. Two-thirds of the states and people are merely spectators to the presidential election.
Another shortcoming of the current system is that a candidate can win the Presidency without winning the most popular votes nationwide.
The National Popular Vote bill has been approved by 18 legislative chambers (one house in Colorado, Arkansas, Maine, North Carolina, Rhode Island, and Washington, and two houses in Maryland, Illinois, Hawaii, California, and Vermont). It has been enacted into law in Hawaii, Illinois, New Jersey, and Maryland. These states have 50 (19%) of the 270 electoral votes needed to bring this legislation into effect.
See http://www.NationalPopularVote.com
susan
Oh Charles, those are English words. Just do a tiny bit of reading for yourself. Go to Wikipedia or to your dictionary.
Oh Charles, those are English words. Just do a tiny bit of reading for yourself. Go to Wikipedia or to your dictionary.
Serves me right for trying to talk to the geeks.
Charles, you were telling the geeks that they needed to screen out cases that just reordered the same states -- as if in the 100 or so posts addressing the homework problem nobody had thought of it. I answered that they did, and used terms from middle school math that said as much: the states were not ordered (nor double counted); they were just a collection of elements that satisfied the criteria that were set.
In a previous life, I had a job that required me to talk to telecommunications engineers. Most of them were thrilled that anyone would want to know the guts of PCM vs. TCP/IP, but occasionally I'd run into a curmudgeon like "Anonynous."
Maybe there's a friendlier geek who'd like to comment on my observation without being condescending or pedantic about it. Trust me, I know how stupid I am. I'm not Republican stupid, but stupid I am. At least I admit it.
Anyway, if you have the numbers 1, 2, 3, and you want to know how many ways there are to get to 4, the first answer is seven:
1+1+1+1
1+1+2
1+2+1
1+3
2+1+1
2+2
3+1
But if you add a constraint that says you cannot count rearrangements of the same numbers, the number of solutions drops to four.
1+1+1+1
1+1+2
1+3
2+2
In the prior answers to Nat's homework assignment, I've been reading about billions of combinations. I'm thinking that a whole lot of those combinations are merely rearrangements of the same states.
That's precisely the difference between combination and permutation. Combinations don't have repeats in that sense.
Let me ask my question of Isabel Lugo, who appears to be the smartest contributor here. My experience has been that the smartest people are usually approachable. Every now and then I've met an impatient super-genius, but they're a lot rarer than impatient mere geniuses or (especially) impatient semi-genuises.
Anyway, Isabel, you came up with nearly 51.2 billion combinations. I presume that individual states wouldn't be double-counted, but what about rearrangements of the same states? And would my hunch be correct that, as you add terms to the equation, the number of arrangements goes up much faster than the number of unique combinations?
Oops, a correction:
And would my hunch be correct that, as you add terms to the equation, the number of RE-arrangements goes up much faster than the number of unique combinations?
Brute force.
Think of the states and DC as a 51-bit value.
total = 0
for value = 0 .. 2^51-1
a) is electoral tally >= 270?
b) if any single state
is removed from value,
is the tally < 270?
If a is true and b is false,
then increment total.
However, since Maine and Nebraska are not winner take all states, this problem is not stated correctly.
And no, 2^51 is not that big a number.
And you could accelerate this by pruning. If K is invalid, then any value M such that K AND M == K is also invalid.
csears, how about formulating the elements not as "states" but as "electoral units?" Assign each electoral unit a code and a number signifying the number of electoral votes. AK3, OH20 and so on. When you get to ME, use MZ(x), MY(y). NE would be NZ(x), NY(y). Does that work?
I would like to comment on my little tangle with "Anonymous," because I think it's a microcosm of a serious problem that the Democratic Party has faced for the last 40 years or so.
We Democrats think we are smart, and we're not shy about saying so. I have a sticker on my car, for example, that reads: "Somewhere In Texas, A Village Is Missing Its Idiot." Oddly enough, in purely partisan terms the idiot has been a rip-roaring success, delivering a $2 trillion tax cut to his 1,000 best friends, windfall war and oil profits to the same, and the remaking and wrecking of government programs and policies we all hold dear.
How did that happen? Could it be that, as smart people, we Democrats neglected the need to present our ideas to people we regard as dumber than us? When 10 words would do, we offered 10 pages. And if someone should happen to not know those 10 pages, we scorned them.
So, the other side, which I dare say is just as smart as we are, paid heed to the words of Herman Wouk, author of The Caine Mutiny, who wrote that the U.S. Navy is a system designed by genuises to be operated by idiots.
And what about the idiot public? Could it be that, rather than being stupid, many of these people were simply uninterested in our 10 pages because they had other things on their plates? And maybe (perish the thought) we occasionally missed a few things along the way. Maybe some of the idiot public was reading from a different book.
Simplicity is a stern task-master. Anyone who's played, or listened to someone else playing, the banjo knows what I am talking about. Play fast, and you can make lots of mistakes with few people noticing. Play slow, and you'd better get it just right because every misplayed note will stick out.
I know that this doesn't directly apply to the homework problem, which must be solved by a combination of pure mathematics and applied computer science. But it also should be describable for the non-specialist, just as the Democratic Party platform ought to be. Beware of abusing your customer, because your customer has one vote, same as you and same as me.
Upon re-examination, I see that my idea would need to be rejiggered for NE. You'd use NZ(x) and NX(y), because there is already an NY31. Then, when culling the combinations for repeats, you'd strip off the numbers and comb through the list to cull out recombinations. In other words, a two-step process.
To facilitate the speedy performance of the second step, maybe the first step could be compiled in such a way as to arrange the "unit codes," i.e., the AK, NZ, AR part, in such a way as to make it easier for the software program, in combination with the microprocessor, to cull them.
That, of course, is a computer science application issue, and when it comes to those details I am just as stupid as I am with math.
Charles,
Since Isabel hasn't answered, I'll see if I can take this one: a combination is made up of a set of elements (states, in our case), without order being taken into consideration. a permutation is a specific ordering of that combination. For instance, to pick 5 out of 51 states, there are ~2.3 million combinations, and each of those combinations could be ordered in (5x4x3x2)=120 different ways, leading to ~282 million permutations. So, when we say 51.2 trillion unique combinations, we mean exactly that. If every different ordering were under consideration, the answer would likely be closer to 10^38 permutations rather than 10^13. Hope this helps.
Charles,
To answer your original question, the answer of 51.199 trillion does /not/ count the rearrangements multiple times: a solution of the form CA, FL, ... is the same as a solution of the form FL, CA, .... In the code I posted, the program considers states only in alphabetical order, which prevents it from counting the same solution multiple times. (The C++ code posted previously uses the same technique.) Isabel's method also avoids double-counting rearrangements, although using a different technique.
eric and brian, thanks much for your answers. I appreciate your having taken the time to answer me in terms I can understand. It's truly mind-boggling that there are 51 trillion (not billion) answers to the question. Holy cow.
Also for the brute force approach, instead of an iteration from 0..2^51-1, you can look at a binary tree traversal. At any node, if the value of the boolean function is true, then any nodes below that can be ignored since they would only add EVs to the tally.
This pruning means it could probably be done on a single machine.
Charles,
I don't know if I'd call myself a "super-genius"...
but yes, the rearrangement issue is something that my solution takes into account. As you can see, my solution involves a rather large polynomial. The big numbers are confusing, so let's consider a smaller example. Let there be a nation in which there are three states, which have three, four, and five electoral votes respectively. (For the sake of giving things names, I'll call these states Wyoming, Idaho, and Utah respectively.) This nation corresponds to the polynomial
(1 + x^3) (1 + x^4) (1 + x^5)
in an obvious way. Multiplying this out gives
1 + x^3 + x^4 + x^5 + x^7 + x^8 + x^9 + x^12
which tells us that there is one way to pick a set of those states that has zero electoral votes (namely, picking none of them), one way to pick a set which has 3 EV (Wyoming only), etc.
Now, the fact that no set is counted twice here just comes out of the way the multiplication process works. We could write this as
(1 + WY) (1 + ID) (1 + UT)
and then the product is
1 + WY + ID + UT + WY*ID + WY*UT + ID*UT + WY*ID*UT
and if we replace each state's name with x raised to the power of its number of electoral votes, we get back the old polynomial. But you see that WY*ID, for example, occurs only once -- we don't also get ID*WY. The reason for that is because in order to expand the product, we pick either the 1 or the WY from the first factor, either the 1 or the ID from the second factor, and either the 1 or the UT from the third factor.
The actual 51-state solution has the same property, just on a larger scale.
Thanks very much, Isabel.
I have a program that works. I'll get it running and post results whenever it finishes.
For the following test set:
[7, 4, 3, 3, 2, 1, 1]
The condition is when sum >= 11. My program spits out a count of 10, the correct number, and the following solutions:
combos =
7 4 0 0 0 0 0
7 0 3 3 0 0 0
7 0 3 0 2 0 0
7 0 3 0 0 1 0
7 0 3 0 0 0 1
7 0 0 3 0 0 1
7 0 0 0 2 1 1
0 4 3 3 0 0 1
0 4 3 0 2 1 1
0 4 0 3 2 1 1
Pleas help check to make sure it is right.
10 isn't the right number,
13 is, I believe.
All combinations, with the ones you're missing :
7 4 0 0 0 0 0
7 0 3 3 0 0 0
7 0 3 0 2 0 0
7 0 0 3 2 0 0 -- missing
7 0 3 0 0 1 0
7 0 3 0 0 0 1
7 0 0 3 0 1 0 -- missing
7 0 0 3 0 0 1
7 0 0 0 2 1 1
0 4 3 3 0 1 0 -- missing
0 4 3 3 0 0 1
0 4 3 0 2 1 1
0 4 0 3 2 1 1
Here's the solution I used, which was pretty easy to code. First, sort all the states by EV in descending order. Think of the problem as a decision tree. First, keep on adding states down the set until you get just above 270. That means that no further choices down that branch will work, because they will have more states than necessary. So you change that choice to a 0, then proceed down the other branch. Whenever you reach the end of all 51 states, you just backtrack to the last "yes" (or 1) state and continue the search down the "no" path. This does an complete search, but with shortcuts whenever possible.
Thanks randy for pointing that out. Coding mistake. I think I've corrected it, and it seems that there are 14 solutions:
combos =
7 4 0 0 0 0 0
7 0 3 3 0 0 0
7 0 3 0 2 0 0
7 0 3 0 0 1 0
7 0 3 0 0 0 1
7 0 0 3 2 0 0
7 0 0 3 0 1 0
7 0 0 3 0 0 1
7 0 0 0 2 1 1
0 4 3 3 2 0 0
0 4 3 3 0 1 0
0 4 3 3 0 0 1
0 4 3 0 2 1 1
0 4 0 3 2 1 1
Yeah, I was just going to post my error there. :-) 14 seems right.
Thanks!
Well, my solution certainly is taking awhile to run! I must say that I like Isabel's solution a lot. Very elegant and mathematical. I guess mine is more of the computer programming approach. Whenever it's done, I'll post the results and see if it matches Isabel's.
I should also mention that after a certain number of the biggest states has been exhausted (I think 11), the remaining don't add up to 270, so that remaining huge branch can be shortcircuited. Thanks to the anonymous poster who pointed it out, it's a great termination condition.
The very interesting contrast of approaches here reminds me of a different context. An American friend of mine first visited the Landau Institute for Theoretical Physics in Leningrad (St. Petersburg) in ca. 1985 to give some lectures and meet with scientists there. Afterwards I asked him how the physics there compared with the physics that he was doing in the U.S.
He replied that the physics was the same from a theoretical perspective but differed a lot in how they went about proving things. The Russians were better formally, i.e., as mathematicians, than the Americans; but the Americans were better at simulating and experimenting to find solutions. He conjectured that this was probably largely an effect of differences in available technological tools. Whereas Americans were used to writing code and getting their answers through brute force, computing power, and trial and error, the Russians had far more limited access to computers and so did most of their work simply via math using paper and pencil or a chalkboard.
The solutions to the homework assignment that Nate set out here is an impressive illustration of these difference in research style (even if Isabel's mathematical representation was supplemented by a computer to carry out the detailed calculations).
It was enormously stimulating to watch the community interacting here, not to mention to see the result!
Above it seems people said there were < 300 possibilities.
I just ran the test with 10 states as "battleground" states (OH, MI, VA, MO, WI, CO, IA, NM, NV, NH), counted 17 states as "safe" (HI, CA, OR, WA, MN, IL, PA, DC, MD, DE, NJ, NY, CT, RI, MA, VT, ME), and the other 24 as "out of reach." and came up with 113 possibilities.
If you substitute out just one of the states I counted "safe" with one I counted as "out of reach", you'd come up with roughly as many entirely new scenarios... so there are way more than 300 scenarios possible. Anyway, I'd say there are 113 "likely" and minimally sufficient scenarios for the Democrats.
That's an interesting story, juris! I just wanted to say that it was taking too much time (>30 min) and processing, so I'll run it when I leave from work and post the answer tomorrow.
I must admit, having powerful computational tools does in some sense make me feel "lazy" sometimes about math. Since I've been working with Matlab all day, it's easy to write up a simple code (about 30 lines) and just let the computer do the rest. Unfortunately, it takes much longer computationally.
I find myself reaching for the calculator sometimes even for what should be easy calculations I could do in my head. I notice that in other people my generation as well.
Oy. Programmers you people aren't. Here's a simple, optimal solution in C (with indentation missing due to the crappy html support here) of the "test case", written and debugged in about 15 minutes; just change NEEDED to 270 and put the state names and EV's into ents to get the real version:
#include <stdio.h>
typedef struct {
char const* name;
int v;
} Ent;
#define NEEDED 11
static Ent ents[] = {
{"7", 7}, {"4", 4}, {"3a", 3}, {"3b", 3}, {"2", 2}, {"1a", 1}, {"1b", 1}
};
#define NENTS (sizeof(ents)/sizeof(*ents))
static int tot = 0;
static int sol[NENTS];
static int avail[NENTS];
static void doit(int n, int a)
{
if( tot >= NEEDED ){
for( int i = 0; i < n; i++ )
printf("%s ", ents[sol[i]].name);
printf("= %d\n", tot);
return;
}
while( a < NENTS ){
int x = avail[a];
int v = ents[x].v;
sol[n] = x;
tot += v;
doit(n+1, ++a);
tot -= v;
}
}
int main(void)
{
for( int i = 0; i < NENTS; i++ )
avail[i] = i;
doit(0, 0);
return 0;
}
This yields the following 14 solutions:
7 4 = 11
7 3a 3b = 13
7 3a 2 = 12
7 3a 1a = 11
7 3a 1b = 11
7 3b 2 = 12
7 3b 1a = 11
7 3b 1b = 11
7 2 1a 1b = 11
4 3a 3b 2 = 12
4 3a 3b 1a = 11
4 3a 3b 1b = 11
4 3a 2 1a 1b = 11
4 3b 2 1a 1b = 11
This is a generalized version of the "subset sum" problem in computer science and it is NP-hard, which in English means that it's extremely difficult to figure out the answer exactly.
First, this problem is neither NP-hard nor NP-complete, it's O(N^2). Second, that not what NP-hard means, not even close.
Oops, sorry, O(n!), not O(n^2) -- it's a combinatorial problem.
Correction to my above: my program was not as good as jqb's, and it was double counting situations involving NH and either NV or NM. The correct total is 104.
Also, for any set of 12 or fewer states, the main page of 270towin.com will show you the number of minimally sufficient winning combinations.
Okay, so it would seem that there are somewhere between 300 and 51 trillion solutions. We're getting somewhere. ;-)
P.S. The "avail" array is an unnecessary artifact (a result of a mistaken approach from somewhere in my first 5 minutes of working on this), so here is some simpler code, with entries for the states (not dealing with the splits), and indentation restored via the miracle of non-breaking spaces (and I realize that the real problem is to count the solutions, not enumerate them, but that has already seen more than one elegant solution):
#include <stdio.h>
typedef struct {
char const* name;
int v;
} Ent;
#define NEEDED 270
static Ent ents[] = {
{"AL", 9}, {"AK", 3}, {"AR", 10}, {"AZ", 6}, {"CA", 55}, {"CO", 9},
{"CT", 7}, {"DE", 3}, {"DC", 3}, {"FL", 27}, {"GA", 15}, {"HI", 4},
{"ID", 4}, {"IL", 21}, {"IN", 11}, {"IA", 7}, {"KS", 6}, {"KY", 8},
{"LA", 9}, {"ME", 4}, {"MD", 10}, {"MA", 12}, {"MI", 17}, {"MN", 10},
{"MS", 6}, {"MO", 11}, {"MT", 3}, {"NE", 5}, {"NV", 5}, {"NH", 4},
{"NJ", 15}, {"NM", 5}, {"NY", 31}, {"NC", 15}, {"ND", 3}, {"OH", 20},
{"OK", 7}, {"OR", 7}, {"PA", 21}, {"RI", 4}, {"SC", 8}, {"SD", 3},
{"TN", 11}, {"TX", 34}, {"UT", 5}, {"VT", 3}, {"VA", 13}, {"WA", 11},
{"WV", 5}, {"WI", 10}, {"WY", 3}
};
#define NENTS (sizeof(ents)/sizeof(*ents))
static int tot = 0;
static int sol[NENTS];
static void doit(int n, int a)
{
if( tot >= NEEDED ){
for( int i = 0; i < n; i++ )
printf("%s ", ents[sol[i]].name);
printf("= %d\n", tot);
return;
}
while( a < NENTS ){
int v = ents[a].v;
sol[n] = a++;
tot += v;
doit(n+1, a);
tot -= v;
}
}
int main(void)
{
doit(0, 0);
return 0;
}
I've produced over 34 billion solutions; it will be a while before it finishes, at which point I'll post them here.
(Get checked for one of the A's if you believed I would really post them.)
Maybe there's a friendlier geek who'd like to comment on my observation without being condescending or pedantic about it.
How ironic (or rather, hypocritical) from someone who lectures others at length and painfully explains something he barely understands to those who understand it well.
My program to enumerate all the combinations is simple because it employs the powerful tool of recursion. doit() is specified as taking a list (sol) of states for which the EC total has been calculated, and a list of available states (a suffix of ents), and produces all the solutions that can be generated by adding members of the second list to the first. Aside from calling doit() from main with an empty sol list and all the states available, all that remains is to implement doit() in terms of itself: If the total is >= NEEDED, sol contains a solution and is printed out, and doit() returns (because adding any more states would be superfluous). Otherwise, all the solutions that include the elements of sol are generated by removing each element from the second list in turn, adding it to sol, and using doit() recursively to produce the solutions for the resulting lists.
Because the states are peeled off ents in order, the printed solutions have the states in the original order given by ents, which need not be sorted in any particular order.
My program has now produced over 2^36 solutions. At this rate, it should be done in less than 4 years.
How ironic (or rather, hypocritical) from someone who lectures others at length and painfully explains something he barely understands to those who understand it well.
But jqb, I lecture in English, and when it comes to anything I've written about the homework problem I think it ought to be pretty clear that I know I can't solve it. I'm only trying to understand it, that's all. Please forgive me.
The correct total is 104.
That's not what I get:
24 out of reach: AL AK AR AZ FL GA ID IN KS KY LA MS MT NE NC ND OK SC SD TN TX UT WV WY
10 battleground: CO IA MI MO NV NH NM OH VA WI
17 safe: CA CT DE DC HI IL ME MD MA MN NJ NY OR PA RI VT WA = 221, 270 needed
AL AK AR AZ CA = 270
AL AK AR AZ CO CT = 274
AL AK AR AZ CO DE = 289
AL AK AR AZ CO DC = 282
AL AK AR AZ CO FL = 279
AL AK AR AZ CT = 270
AL AK AR AZ DE = 285
AL AK AR AZ DC = 278
AL AK AR AZ FL = 275
AL AK AR CA CO CT DE = 288
AL AK AR CA CO CT DC = 281
AL AK AR CA CO CT FL = 278
AL AK AR CA CO DE = 283
AL AK AR CA CO DC = 276
AL AK AR CA CO FL = 273
AL AK AR CA CT DE = 284
AL AK AR CA CT DC = 277
AL AK AR CA CT FL = 274
AL AK AR CA DE = 279
AL AK AR CA DC = 272
AL AK AR CO CT DE = 283
AL AK AR CO CT DC = 276
AL AK AR CO CT FL = 273
AL AK AR CO DE = 278
AL AK AR CO DC = 271
AL AK AR CT DE = 279
AL AK AR CT DC = 272
AL AK AR DE = 274
AL AK AR DC FL = 277
AL AK AZ CA CO CT DE = 282
AL AK AZ CA CO CT DC = 275
AL AK AZ CA CO CT FL = 272
AL AK AZ CA CO DE = 277
AL AK AZ CA CO DC = 270
AL AK AZ CA CT DE = 278
AL AK AZ CA CT DC = 271
AL AK AZ CA DE = 273
AL AK AZ CA DC FL = 276
AL AK AZ CO CT DE = 277
AL AK AZ CO CT DC = 270
AL AK AZ CO DE = 272
AL AK AZ CO DC FL = 275
AL AK AZ CT DE = 273
AL AK AZ CT DC FL = 276
AL AK AZ DE DC = 281
AL AK AZ DE FL = 278
AL AK AZ DC FL = 271
AL AK CA CO CT DE = 271
AL AK CA CO CT DC FL = 274
AL AK CA CO DE DC = 279
AL AK CA CO DE FL = 276
AL AK CA CT DE DC = 280
AL AK CA CT DE FL = 277
AL AK CA CT DC FL = 270
AL AK CA DE DC = 275
AL AK CA DE FL = 272
AL AK CO CT DE DC = 279
AL AK CO CT DE FL = 276
AL AK CO DE DC = 274
AL AK CO DE FL = 271
AL AK CT DE DC = 275
AL AK CT DE FL = 272
AL AK DE DC = 270
AL AR AZ CA CO CT = 272
AL AR AZ CA CO DE = 287
AL AR AZ CA CO DC = 280
AL AR AZ CA CO FL = 277
AL AR AZ CA CT DE = 288
AL AR AZ CA CT DC = 281
AL AR AZ CA CT FL = 278
AL AR AZ CA DE = 283
AL AR AZ CA DC = 276
AL AR AZ CA FL = 273
AL AR AZ CO CT DE = 287
AL AR AZ CO CT DC = 280
AL AR AZ CO CT FL = 277
AL AR AZ CO DE = 282
AL AR AZ CO DC = 275
AL AR AZ CO FL = 272
AL AR AZ CT DE = 283
AL AR AZ CT DC = 276
AL AR AZ CT FL = 273
AL AR AZ DE = 278
AL AR AZ DC = 271
AL AR CA CO CT DE = 281
AL AR CA CO CT DC = 274
AL AR CA CO CT FL = 271
AL AR CA CO DE = 276
AL AR CA CO DC FL = 279
AL AR CA CT DE = 277
AL AR CA CT DC = 270
AL AR CA DE = 272
AL AR CA DC FL = 275
AL AR CO CT DE = 276
AL AR CO CT DC FL = 279
AL AR CO DE = 271
AL AR CO DC FL = 274
AL AR CT DE = 272
AL AR CT DC FL = 275
AL AR DE DC = 280
AL AR DE FL = 277
AL AR DC FL = 270
AL AZ CA CO CT DE = 275
AL AZ CA CO CT DC FL = 278
AL AZ CA CO DE = 270
AL AZ CA CO DC FL = 273
AL AZ CA CT DE = 271
AL AZ CA CT DC FL = 274
AL AZ CA DE DC = 279
AL AZ CA DE FL = 276
AL AZ CO CT DE = 270
AL AZ CO CT DC FL = 273
AL AZ CO DE DC = 278
AL AZ CO DE FL = 275
AL AZ CT DE DC = 279
AL AZ CT DE FL = 276
AL AZ DE DC = 274
AL AZ DE FL = 271
AL CA CO CT DE DC = 277
AL CA CO CT DE FL = 274
AL CA CO DE DC = 272
AL CA CT DE DC = 273
AL CA CT DE FL = 270
AL CA DE DC FL = 278
AL CO CT DE DC = 272
AL CO DE DC FL = 277
AL CT DE DC FL = 278
AL DE DC FL = 273
AK AR AZ CA CO CT = 270
AK AR AZ CA CO DE = 285
AK AR AZ CA CO DC = 278
AK AR AZ CA CO FL = 275
AK AR AZ CA CT DE = 286
AK AR AZ CA CT DC = 279
AK AR AZ CA CT FL = 276
AK AR AZ CA DE = 281
AK AR AZ CA DC = 274
AK AR AZ CA FL = 271
AK AR AZ CO CT DE = 285
AK AR AZ CO CT DC = 278
AK AR AZ CO CT FL = 275
AK AR AZ CO DE = 280
AK AR AZ CO DC = 273
AK AR AZ CO FL = 270
AK AR AZ CT DE = 281
AK AR AZ CT DC = 274
AK AR AZ CT FL = 271
AK AR AZ DE = 276
AK AR AZ DC FL = 279
AK AR CA CO CT DE = 279
AK AR CA CO CT DC = 272
AK AR CA CO DE = 274
AK AR CA CO DC FL = 277
AK AR CA CT DE = 275
AK AR CA CT DC FL = 278
AK AR CA DE = 270
AK AR CA DC FL = 273
AK AR CO CT DE = 274
AK AR CO CT DC FL = 277
AK AR CO DE DC = 282
AK AR CO DE FL = 279
AK AR CO DC FL = 272
AK AR CT DE = 270
AK AR CT DC FL = 273
AK AR DE DC = 278
AK AR DE FL = 275
AK AZ CA CO CT DE = 273
AK AZ CA CO CT DC FL = 276
AK AZ CA CO DE DC = 281
AK AZ CA CO DE FL = 278
AK AZ CA CO DC FL = 271
AK AZ CA CT DE DC = 282
AK AZ CA CT DE FL = 279
AK AZ CA CT DC FL = 272
AK AZ CA DE DC = 277
AK AZ CA DE FL = 274
AK AZ CO CT DE DC = 281
AK AZ CO CT DE FL = 278
AK AZ CO CT DC FL = 271
AK AZ CO DE DC = 276
AK AZ CO DE FL = 273
AK AZ CT DE DC = 277
AK AZ CT DE FL = 274
AK AZ DE DC = 272
AK CA CO CT DE DC = 275
AK CA CO CT DE FL = 272
AK CA CO DE DC = 270
AK CA CT DE DC = 271
AK CA DE DC FL = 276
AK CO CT DE DC = 270
AK CO DE DC FL = 275
AK CT DE DC FL = 276
AK DE DC FL = 271
AR AZ CA CO CT DE = 283
AR AZ CA CO CT DC = 276
AR AZ CA CO CT FL = 273
AR AZ CA CO DE = 278
AR AZ CA CO DC = 271
AR AZ CA CT DE = 279
AR AZ CA CT DC = 272
AR AZ CA DE = 274
AR AZ CA DC FL = 277
AR AZ CO CT DE = 278
AR AZ CO CT DC = 271
AR AZ CO DE = 273
AR AZ CO DC FL = 276
AR AZ CT DE = 274
AR AZ CT DC FL = 277
AR AZ DE DC = 282
AR AZ DE FL = 279
AR AZ DC FL = 272
AR CA CO CT DE = 272
AR CA CO CT DC FL = 275
AR CA CO DE DC = 280
AR CA CO DE FL = 277
AR CA CO DC FL = 270
AR CA CT DE DC = 281
AR CA CT DE FL = 278
AR CA CT DC FL = 271
AR CA DE DC = 276
AR CA DE FL = 273
AR CO CT DE DC = 280
AR CO CT DE FL = 277
AR CO CT DC FL = 270
AR CO DE DC = 275
AR CO DE FL = 272
AR CT DE DC = 276
AR CT DE FL = 273
AR DE DC = 271
AZ CA CO CT DE DC = 279
AZ CA CO CT DE FL = 276
AZ CA CO DE DC = 274
AZ CA CO DE FL = 271
AZ CA CT DE DC = 275
AZ CA CT DE FL = 272
AZ CA DE DC = 270
AZ CO CT DE DC = 274
AZ CO CT DE FL = 271
AZ CO DE DC FL = 279
AZ CT DE DC = 270
AZ DE DC FL = 275
CA CO CT DE DC FL = 278
CA CO DE DC FL = 273
CA CT DE DC FL = 274
CO CT DE DC FL = 273
245 solutions
Here's the program that produced the results above. The SAFE/OUT/BATTLE status of the states can easily be changed:
#include <stdio.h>
typedef struct {
char const* name;
int v;
int type;
} Ent;
enum { SAFE, OUT, BATTLE };
static Ent ents[] = {
{"AL", 9, OUT}, {"AK", 3, OUT}, {"AR", 10, OUT}, {"AZ", 6, OUT}, {"CA", 55, SAFE}, {"CO", 9, BATTLE},
{"CT", 7, SAFE}, {"DE", 3, SAFE}, {"DC", 3, SAFE}, {"FL", 27, OUT}, {"GA", 15, OUT}, {"HI", 4, SAFE},
{"ID", 4, OUT}, {"IL", 21, SAFE}, {"IN", 11, OUT}, {"IA", 7, BATTLE}, {"KS", 6, OUT}, {"KY", 8, OUT},
{"LA", 9, OUT}, {"ME", 4, SAFE}, {"MD", 10, SAFE}, {"MA", 12, SAFE}, {"MI", 17, BATTLE}, {"MN", 10, SAFE},
{"MS", 6, OUT}, {"MO", 11, BATTLE}, {"MT", 3, OUT}, {"NE", 5, OUT}, {"NV", 5, BATTLE}, {"NH", 4, BATTLE},
{"NJ", 15, SAFE}, {"NM", 5, BATTLE}, {"NY", 31, SAFE}, {"NC", 15, OUT}, {"ND", 3, OUT}, {"OH", 20, BATTLE},
{"OK", 7, OUT}, {"OR", 7, SAFE}, {"PA", 21, SAFE}, {"RI", 4, SAFE}, {"SC", 8, OUT}, {"SD", 3, OUT},
{"TN", 11, OUT}, {"TX", 34, OUT}, {"UT", 5, OUT}, {"VT", 3, SAFE}, {"VA", 13, BATTLE}, {"WA", 11, SAFE},
{"WV", 5, OUT}, {"WI", 10, BATTLE}, {"WY", 3, OUT}
};
#define NENTS (sizeof(ents)/sizeof(*ents))
static int needed = 0;
static int tot = 0;
static int sol[NENTS];
static int bat[NENTS];
static int nbat = 0;
static int nsol = 0;
static void doit(int n, int a)
{
if( tot >= needed ){
for( int i = 0; i < n; i++ )
printf("%s ", ents[sol[i]].name);
printf("= %d\n", tot);
nsol++;
return;
}
while( a < nbat ){
int v = ents[bat[a]].v;
sol[n] = a++;
tot += v;
doit(n+1, a);
tot -= v;
}
}
static void prents(int type)
{
for( int i = 0; i < NENTS; i++ )
if( ents[i].type == type )
printf(" %s", ents[i].name);
}
int main(void)
{
int nsafe = 0, nout = 0;
for( int i = 0; i < NENTS; i++ ){
needed += ents[i].v;
switch( ents[i].type ){
case SAFE:
tot += ents[i].v;
nsafe++;
break;
case OUT:
nout++;
break;
case BATTLE:
bat[nbat++] = i;
break;
}
}
needed = needed/2 + 1;
printf("%d out of reach:", nout);
prents(OUT);
printf("\n%d battleground:", nbat);
prents(BATTLE);
printf("\n%d safe:", nsafe);
prents(SAFE);
printf(" = %d, %d needed\n", tot, needed);
doit(0, 0);
printf("%d solutions\n", nsol);
return 0;
}
Not sure what your list is of, but clearly it's of something different. A random selection:
AR CA CT DE DC = 281
None of those are battleground states. Also, you could subtract all but CA and still have 270, so it's not a minimal solution...
None of those are battleground states.
Indeed, I screwed up the indices, and the results are redundant. Fixing the former is easy; I need to figure the latter.
Ok, I had failed to see the importance of sorting by decreasing vote count. Sorry to have been so dense, and so sloppy that I didn't even notice how absurd the results were. Here are my new results, which agree with Adam's count of 104; code to follow:
17 safe: CA CT DE DC HI IL ME MD MA MN NJ NY OR PA RI VT WA = 221, 49 more needed
24 out of reach: AL AK AR AZ FL GA ID IN KS KY LA MS MT NE NC ND OK SC SD TN TX UT WV WY = 216
10 battleground: CO IA MI MO NV NH NM OH VA WI = 101
OH MI VA = 50 (271)
OH MI MO WI = 58 (279)
OH MI MO CO = 57 (278)
OH MI MO IA = 55 (276)
OH MI MO NV = 53 (274)
OH MI MO NM = 53 (274)
OH MI MO NH = 52 (273)
OH MI WI CO = 56 (277)
OH MI WI IA = 54 (275)
OH MI WI NV = 52 (273)
OH MI WI NM = 52 (273)
OH MI WI NH = 51 (272)
OH MI CO IA = 53 (274)
OH MI CO NV = 51 (272)
OH MI CO NM = 51 (272)
OH MI CO NH = 50 (271)
OH MI IA NV = 49 (270)
OH MI IA NM = 49 (270)
OH MI NV NM NH = 51 (272)
OH VA MO WI = 54 (275)
OH VA MO CO = 53 (274)
OH VA MO IA = 51 (272)
OH VA MO NV = 49 (270)
OH VA MO NM = 49 (270)
OH VA WI CO = 52 (273)
OH VA WI IA = 50 (271)
OH VA WI NV NM = 53 (274)
OH VA WI NV NH = 52 (273)
OH VA WI NM NH = 52 (273)
OH VA CO IA = 49 (270)
OH VA CO NV NM = 52 (273)
OH VA CO NV NH = 51 (272)
OH VA CO NM NH = 51 (272)
OH VA IA NV NM = 50 (271)
OH VA IA NV NH = 49 (270)
OH VA IA NM NH = 49 (270)
OH MO WI CO = 50 (271)
OH MO WI IA NV = 53 (274)
OH MO WI IA NM = 53 (274)
OH MO WI IA NH = 52 (273)
OH MO WI NV NM = 51 (272)
OH MO WI NV NH = 50 (271)
OH MO WI NM NH = 50 (271)
OH MO CO IA NV = 52 (273)
OH MO CO IA NM = 52 (273)
OH MO CO IA NH = 51 (272)
OH MO CO NV NM = 50 (271)
OH MO CO NV NH = 49 (270)
OH MO CO NM NH = 49 (270)
OH MO IA NV NM NH = 52 (273)
OH WI CO IA NV = 51 (272)
OH WI CO IA NM = 51 (272)
OH WI CO IA NH = 50 (271)
OH WI CO NV NM = 49 (270)
OH WI IA NV NM NH = 51 (272)
OH CO IA NV NM NH = 50 (271)
MI VA MO WI = 51 (272)
MI VA MO CO = 50 (271)
MI VA MO IA NV = 53 (274)
MI VA MO IA NM = 53 (274)
MI VA MO IA NH = 52 (273)
MI VA MO NV NM = 51 (272)
MI VA MO NV NH = 50 (271)
MI VA MO NM NH = 50 (271)
MI VA WI CO = 49 (270)
MI VA WI IA NV = 52 (273)
MI VA WI IA NM = 52 (273)
MI VA WI IA NH = 51 (272)
MI VA WI NV NM = 50 (271)
MI VA WI NV NH = 49 (270)
MI VA WI NM NH = 49 (270)
MI VA CO IA NV = 51 (272)
MI VA CO IA NM = 51 (272)
MI VA CO IA NH = 50 (271)
MI VA CO NV NM = 49 (270)
MI VA IA NV NM NH = 51 (272)
MI MO WI CO IA = 54 (275)
MI MO WI CO NV = 52 (273)
MI MO WI CO NM = 52 (273)
MI MO WI CO NH = 51 (272)
MI MO WI IA NV = 50 (271)
MI MO WI IA NM = 50 (271)
MI MO WI IA NH = 49 (270)
MI MO WI NV NM NH = 52 (273)
MI MO CO IA NV = 49 (270)
MI MO CO IA NM = 49 (270)
MI MO CO NV NM NH = 51 (272)
MI MO IA NV NM NH = 49 (270)
MI WI CO IA NV NM = 53 (274)
MI WI CO IA NV NH = 52 (273)
MI WI CO IA NM NH = 52 (273)
MI WI CO NV NM NH = 50 (271)
VA MO WI CO IA = 50 (271)
VA MO WI CO NV NM = 53 (274)
VA MO WI CO NV NH = 52 (273)
VA MO WI CO NM NH = 52 (273)
VA MO WI IA NV NM = 51 (272)
VA MO WI IA NV NH = 50 (271)
VA MO WI IA NM NH = 50 (271)
VA MO CO IA NV NM = 50 (271)
VA MO CO IA NV NH = 49 (270)
VA MO CO IA NM NH = 49 (270)
VA WI CO IA NV NM = 49 (270)
MO WI CO IA NV NM NH = 51 (272)
104 solutions
Code that produced the results above:
#include <stdio.h>
#include <stdlib.h>
typedef struct {
char const* name;
int v;
int type;
} Ent;
enum { SAFE, OUT, BAT };
static int n_of[3];
static int v_of[3];
static Ent ents[] = {
{"AL", 9, OUT}, {"AK", 3, OUT}, {"AR", 10, OUT}, {"AZ", 6, OUT},
{"CA", 55, SAFE}, {"CO", 9, BAT}, {"CT", 7, SAFE}, {"DE", 3, SAFE},
{"DC", 3, SAFE}, {"FL", 27, OUT}, {"GA", 15, OUT}, {"HI", 4, SAFE},
{"ID", 4, OUT}, {"IL", 21, SAFE}, {"IN", 11, OUT}, {"IA", 7, BAT},
{"KS", 6, OUT}, {"KY", 8, OUT}, {"LA", 9, OUT}, {"ME", 4, SAFE},
{"MD", 10, SAFE}, {"MA", 12, SAFE}, {"MI", 17, BAT}, {"MN", 10, SAFE},
{"MS", 6, OUT}, {"MO", 11, BAT}, {"MT", 3, OUT}, {"NE", 5, OUT},
{"NV", 5, BAT}, {"NH", 4, BAT}, {"NJ", 15, SAFE}, {"NM", 5, BAT},
{"NY", 31, SAFE}, {"NC", 15, OUT}, {"ND", 3, OUT}, {"OH", 20, BAT},
{"OK", 7, OUT}, {"OR", 7, SAFE}, {"PA", 21, SAFE}, {"RI", 4, SAFE},
{"SC", 8, OUT}, {"SD", 3, OUT}, {"TN", 11, OUT}, {"TX", 34, OUT},
{"UT", 5, OUT}, {"VT", 3, SAFE}, {"VA", 13, BAT}, {"WA", 11, SAFE},
{"WV", 5, OUT}, {"WI", 10, BAT}, {"WY", 3, OUT}
};
#define NENTS (sizeof(ents)/sizeof(*ents))
static int needed = 0;
static int tot = 0;
static int nsol = 0;
static int sol[NENTS];
static int bat[NENTS];
static void doit(int n, int a)
{
if( tot >= needed ){
for( int i = 0; i < n; i++ )
printf("%s ", ents[sol[i]].name);
printf("= %d (%d)\n", tot, tot+v_of[SAFE]);
nsol++;
return;
}
while( a < n_of[BAT] ){
sol[n] = bat[a++];
int v = ents[sol[n]].v;
tot += v;
doit(n+1, a);
tot -= v;
}
}
static void prents(char const* s, int t)
{
printf("%d %s:", n_of[t], s);
for( int i = 0; i < NENTS; i++ )
if( ents[i].type == t )
printf(" %s", ents[i].name);
printf(" = %d", v_of[t]);
if( t == SAFE ) printf(", %d more needed", needed);
printf("\n");
}
static int cmp(void const* a, void const* b)
{
return ents[*(int*)b].v - ents[*(int*)a].v;
}
int main(void)
{
for( int i = 0; i < NENTS; i++ ){
int t = ents[i].type;
if( t == BAT ) bat[n_of[BAT]] = i;
n_of[t]++;
v_of[t] += ents[i].v;
needed += ents[i].v;
}
needed = needed/2 + 1 - v_of[SAFE];
prents("safe", SAFE);
prents("out of reach", OUT);
prents("battleground", BAT);
qsort(bat, n_of[BAT], sizeof *bat, cmp);
doit(0, 0);
printf("%d solutions\n", nsol);
return 0;
}
Here is a quick way to enumerate 184,320 combinations:
One 3-vote state (8 choices)
One 4-vote state (5 choices)
One 5-vote state (4 choices)
One 6-vote state (3 choices)
One 7-vote state (4 choices)
One 9-vote state (2 choices)
Two 10-vote states(4 choices)
One 11-vote state (4 choices)
Michigan, Ohio, PA or IL, Florida, New York, Texas, California.
To get the total number, multiply the number of choices for each slot (for 10-vote states, multiply by 4 choose 2, or 6).
Get more choices by substituting a 9-vote state with three 3-vote states, and get an additional 806,400 choices. So there you go, over 1 million right there.
So there you go, over 1 million right there.
We've been way past that for more than a day, since Brian gave the approximate solution of 51.3 trillion, later refined by Isabel Lugo to exactly 51,199,463,116,367.
Looking back at the beginning of the thread, I also see that "anonymous" should get credit as the first to give a correct and efficient algorithm, which s/he characterized as "greedy bin packing". It's a pity I didn't see that or pay attention to it, as my own code, which operates along the same lines, omitted the important first step of "sort by decreasing weight" until Adam pointed out my redundant results.
Again looking back at the beginning of this thread, it's bizarre to see all the talk of "NP-complete" and "NP-hard", which is quite inapplicable to the problem here. It's as if people were taught these terms but not given any sort of conceptual framework for understanding them or their application. The terms apply to the computational complexity of algorithms for finding rare solutions within large spaces ... usually optimization problems, such as the shortest path for a traveling salesperson, or how to pack things into bins with the least wasted space. But the original problem here is produce a count of solutions, not to find one with special characteristics ... it simply isn't the sort of thing to which these terms apply. And enumerating all the solutions isn't an optimization problem; you can't produce n! results in less than n! time. And finding some solution can easily be done in O(nlogn + n) time by sorting the entries by descending weight and then grabbing the smallest prefix that adds up to >= 270. Only if the problem were to find a set of states where the EC count is >= 270 with some independent constraint -- say, the combined number of letters in the state names is minimal -- would this enter the territory of NP-* problems.
later refined by Isabel Lugo to exactly 51,199,463,116,367
Oops, andras gave that exact answer earlier -- obtained via an undisclosed "quick hack".
So, we know the answer is somewhere between 243 and 50 trillion.
And later
Okay, so it would seem that there are somewhere between 300 and 51 trillion solutions.
These were written after the exact answer, which is more than 51 trillion, was given by more than one person.
Sigh.
I should also mention that after a certain number of the biggest states has been exhausted (I think 11), the remaining don't add up to 270, so that remaining huge branch can be shortcircuited. Thanks to the anonymous poster who pointed it out, it's a great termination condition.
It is indeed, and I've added it to my program (in a general way, of course) -- but I'm not seeing where an anonymous poster pointed it out.
That's an interesting story, juris!
I think the story misses the point, which is that counting solutions and producing them are quite different problems that demand different sorts of solutions -- certainly when the number of solutions is very large. To wit:
I just wanted to say that it was taking too much time (>30 min) and processing, so I'll run it when I leave from work and post the answer tomorrow.
Um, you might want to do a back of the envelope calculation to see how long it's going to take you to enumerate over 51 trillion solutions, given how fast your program is generating them. Unless you've got NSA-level computing power, you won't be done by tomorrow.
that demand different sorts of solutions
Hmmm ... too many "solutions" in that sentence. I should have said "that demand different sorts of algorithms". Consider the remarkably elegant dynamic programming algorithm from anonymous at June 10, 2008 6:38 PM to determine the count ... considerably more elegant than the Haskell program. Even Isabel Lugo's solution using polynomials, while very clever, is not nearly as concise and requires quite a bit of manual work.
I've taken the results from jqb. Considering the battleground states are right, the percetage they appear in a given result is something between 41,35% (NH) to 53,85% (MO).
The most probable states in these results are MO, OH, MI, WI, accounting 58 EVs.
I don't think those probabilities are meaningful in any sense. Those states are simply the ones with the most EV's, with the exclusion of VA for some reason -- but some reason that is entirely number theoretic, not political. One must keep in mind that the "without any excess" constraint is completely artificial; in real life, nothing prevents more states going to Obama than he needs.
To make the point, I ran it with the constraint removed, and now the frequency of the occurrence of a state is, as one should expect, in accord with its number of EVs: OH MI VA MO WI ...
17 safe: CA CT DE DC HI IL ME MD MA MN NJ NY OR PA RI VT WA = 221, 49 more needed
24 out of reach: AL AK AR AZ FL GA ID IN KS KY LA MS MT NE NC ND OK SC SD TN TX UT WV WY = 216
10 in play: CO IA MI MO NV NH NM OH VA WI = 101
OH MI VA = 50 (271)
OH MI VA MO = 61 (282)
OH MI VA MO WI = 71 (292)
OH MI VA MO WI CO = 80 (301)
OH MI VA MO WI CO IA = 87 (308)
OH MI VA MO WI CO IA NV = 92 (313)
OH MI VA MO WI CO IA NV NM = 97 (318)
OH MI VA MO WI CO IA NV NM NH = 101 (322)
OH MI VA MO WI CO IA NV NH = 96 (317)
OH MI VA MO WI CO IA NM = 92 (313)
OH MI VA MO WI CO IA NM NH = 96 (317)
OH MI VA MO WI CO IA NH = 91 (312)
OH MI VA MO WI CO NV = 85 (306)
OH MI VA MO WI CO NV NM = 90 (311)
OH MI VA MO WI CO NV NM NH = 94 (315)
OH MI VA MO WI CO NV NH = 89 (310)
OH MI VA MO WI CO NM = 85 (306)
OH MI VA MO WI CO NM NH = 89 (310)
OH MI VA MO WI CO NH = 84 (305)
OH MI VA MO WI IA = 78 (299)
OH MI VA MO WI IA NV = 83 (304)
OH MI VA MO WI IA NV NM = 88 (309)
OH MI VA MO WI IA NV NM NH = 92 (313)
OH MI VA MO WI IA NV NH = 87 (308)
OH MI VA MO WI IA NM = 83 (304)
OH MI VA MO WI IA NM NH = 87 (308)
OH MI VA MO WI IA NH = 82 (303)
OH MI VA MO WI NV = 76 (297)
OH MI VA MO WI NV NM = 81 (302)
OH MI VA MO WI NV NM NH = 85 (306)
OH MI VA MO WI NV NH = 80 (301)
OH MI VA MO WI NM = 76 (297)
OH MI VA MO WI NM NH = 80 (301)
OH MI VA MO WI NH = 75 (296)
OH MI VA MO CO = 70 (291)
OH MI VA MO CO IA = 77 (298)
OH MI VA MO CO IA NV = 82 (303)
OH MI VA MO CO IA NV NM = 87 (308)
OH MI VA MO CO IA NV NM NH = 91 (312)
OH MI VA MO CO IA NV NH = 86 (307)
OH MI VA MO CO IA NM = 82 (303)
OH MI VA MO CO IA NM NH = 86 (307)
OH MI VA MO CO IA NH = 81 (302)
OH MI VA MO CO NV = 75 (296)
OH MI VA MO CO NV NM = 80 (301)
OH MI VA MO CO NV NM NH = 84 (305)
OH MI VA MO CO NV NH = 79 (300)
OH MI VA MO CO NM = 75 (296)
OH MI VA MO CO NM NH = 79 (300)
OH MI VA MO CO NH = 74 (295)
OH MI VA MO IA = 68 (289)
OH MI VA MO IA NV = 73 (294)
OH MI VA MO IA NV NM = 78 (299)
OH MI VA MO IA NV NM NH = 82 (303)
OH MI VA MO IA NV NH = 77 (298)
OH MI VA MO IA NM = 73 (294)
OH MI VA MO IA NM NH = 77 (298)
OH MI VA MO IA NH = 72 (293)
OH MI VA MO NV = 66 (287)
OH MI VA MO NV NM = 71 (292)
OH MI VA MO NV NM NH = 75 (296)
OH MI VA MO NV NH = 70 (291)
OH MI VA MO NM = 66 (287)
OH MI VA MO NM NH = 70 (291)
OH MI VA MO NH = 65 (286)
OH MI VA WI = 60 (281)
OH MI VA WI CO = 69 (290)
OH MI VA WI CO IA = 76 (297)
OH MI VA WI CO IA NV = 81 (302)
OH MI VA WI CO IA NV NM = 86 (307)
OH MI VA WI CO IA NV NM NH = 90 (311)
OH MI VA WI CO IA NV NH = 85 (306)
OH MI VA WI CO IA NM = 81 (302)
OH MI VA WI CO IA NM NH = 85 (306)
OH MI VA WI CO IA NH = 80 (301)
OH MI VA WI CO NV = 74 (295)
OH MI VA WI CO NV NM = 79 (300)
OH MI VA WI CO NV NM NH = 83 (304)
OH MI VA WI CO NV NH = 78 (299)
OH MI VA WI CO NM = 74 (295)
OH MI VA WI CO NM NH = 78 (299)
OH MI VA WI CO NH = 73 (294)
OH MI VA WI IA = 67 (288)
OH MI VA WI IA NV = 72 (293)
OH MI VA WI IA NV NM = 77 (298)
OH MI VA WI IA NV NM NH = 81 (302)
OH MI VA WI IA NV NH = 76 (297)
OH MI VA WI IA NM = 72 (293)
OH MI VA WI IA NM NH = 76 (297)
OH MI VA WI IA NH = 71 (292)
OH MI VA WI NV = 65 (286)
OH MI VA WI NV NM = 70 (291)
OH MI VA WI NV NM NH = 74 (295)
OH MI VA WI NV NH = 69 (290)
OH MI VA WI NM = 65 (286)
OH MI VA WI NM NH = 69 (290)
OH MI VA WI NH = 64 (285)
OH MI VA CO = 59 (280)
OH MI VA CO IA = 66 (287)
OH MI VA CO IA NV = 71 (292)
OH MI VA CO IA NV NM = 76 (297)
OH MI VA CO IA NV NM NH = 80 (301)
OH MI VA CO IA NV NH = 75 (296)
OH MI VA CO IA NM = 71 (292)
OH MI VA CO IA NM NH = 75 (296)
OH MI VA CO IA NH = 70 (291)
OH MI VA CO NV = 64 (285)
OH MI VA CO NV NM = 69 (290)
OH MI VA CO NV NM NH = 73 (294)
OH MI VA CO NV NH = 68 (289)
OH MI VA CO NM = 64 (285)
OH MI VA CO NM NH = 68 (289)
OH MI VA CO NH = 63 (284)
OH MI VA IA = 57 (278)
OH MI VA IA NV = 62 (283)
OH MI VA IA NV NM = 67 (288)
OH MI VA IA NV NM NH = 71 (292)
OH MI VA IA NV NH = 66 (287)
OH MI VA IA NM = 62 (283)
OH MI VA IA NM NH = 66 (287)
OH MI VA IA NH = 61 (282)
OH MI VA NV = 55 (276)
OH MI VA NV NM = 60 (281)
OH MI VA NV NM NH = 64 (285)
OH MI VA NV NH = 59 (280)
OH MI VA NM = 55 (276)
OH MI VA NM NH = 59 (280)
OH MI VA NH = 54 (275)
OH MI MO WI = 58 (279)
OH MI MO WI CO = 67 (288)
OH MI MO WI CO IA = 74 (295)
OH MI MO WI CO IA NV = 79 (300)
OH MI MO WI CO IA NV NM = 84 (305)
OH MI MO WI CO IA NV NM NH = 88 (309)
OH MI MO WI CO IA NV NH = 83 (304)
OH MI MO WI CO IA NM = 79 (300)
OH MI MO WI CO IA NM NH = 83 (304)
OH MI MO WI CO IA NH = 78 (299)
OH MI MO WI CO NV = 72 (293)
OH MI MO WI CO NV NM = 77 (298)
OH MI MO WI CO NV NM NH = 81 (302)
OH MI MO WI CO NV NH = 76 (297)
OH MI MO WI CO NM = 72 (293)
OH MI MO WI CO NM NH = 76 (297)
OH MI MO WI CO NH = 71 (292)
OH MI MO WI IA = 65 (286)
OH MI MO WI IA NV = 70 (291)
OH MI MO WI IA NV NM = 75 (296)
OH MI MO WI IA NV NM NH = 79 (300)
OH MI MO WI IA NV NH = 74 (295)
OH MI MO WI IA NM = 70 (291)
OH MI MO WI IA NM NH = 74 (295)
OH MI MO WI IA NH = 69 (290)
OH MI MO WI NV = 63 (284)
OH MI MO WI NV NM = 68 (289)
OH MI MO WI NV NM NH = 72 (293)
OH MI MO WI NV NH = 67 (288)
OH MI MO WI NM = 63 (284)
OH MI MO WI NM NH = 67 (288)
OH MI MO WI NH = 62 (283)
OH MI MO CO = 57 (278)
OH MI MO CO IA = 64 (285)
OH MI MO CO IA NV = 69 (290)
OH MI MO CO IA NV NM = 74 (295)
OH MI MO CO IA NV NM NH = 78 (299)
OH MI MO CO IA NV NH = 73 (294)
OH MI MO CO IA NM = 69 (290)
OH MI MO CO IA NM NH = 73 (294)
OH MI MO CO IA NH = 68 (289)
OH MI MO CO NV = 62 (283)
OH MI MO CO NV NM = 67 (288)
OH MI MO CO NV NM NH = 71 (292)
OH MI MO CO NV NH = 66 (287)
OH MI MO CO NM = 62 (283)
OH MI MO CO NM NH = 66 (287)
OH MI MO CO NH = 61 (282)
OH MI MO IA = 55 (276)
OH MI MO IA NV = 60 (281)
OH MI MO IA NV NM = 65 (286)
OH MI MO IA NV NM NH = 69 (290)
OH MI MO IA NV NH = 64 (285)
OH MI MO IA NM = 60 (281)
OH MI MO IA NM NH = 64 (285)
OH MI MO IA NH = 59 (280)
OH MI MO NV = 53 (274)
OH MI MO NV NM = 58 (279)
OH MI MO NV NM NH = 62 (283)
OH MI MO NV NH = 57 (278)
OH MI MO NM = 53 (274)
OH MI MO NM NH = 57 (278)
OH MI MO NH = 52 (273)
OH MI WI CO = 56 (277)
OH MI WI CO IA = 63 (284)
OH MI WI CO IA NV = 68 (289)
OH MI WI CO IA NV NM = 73 (294)
OH MI WI CO IA NV NM NH = 77 (298)
OH MI WI CO IA NV NH = 72 (293)
OH MI WI CO IA NM = 68 (289)
OH MI WI CO IA NM NH = 72 (293)
OH MI WI CO IA NH = 67 (288)
OH MI WI CO NV = 61 (282)
OH MI WI CO NV NM = 66 (287)
OH MI WI CO NV NM NH = 70 (291)
OH MI WI CO NV NH = 65 (286)
OH MI WI CO NM = 61 (282)
OH MI WI CO NM NH = 65 (286)
OH MI WI CO NH = 60 (281)
OH MI WI IA = 54 (275)
OH MI WI IA NV = 59 (280)
OH MI WI IA NV NM = 64 (285)
OH MI WI IA NV NM NH = 68 (289)
OH MI WI IA NV NH = 63 (284)
OH MI WI IA NM = 59 (280)
OH MI WI IA NM NH = 63 (284)
OH MI WI IA NH = 58 (279)
OH MI WI NV = 52 (273)
OH MI WI NV NM = 57 (278)
OH MI WI NV NM NH = 61 (282)
OH MI WI NV NH = 56 (277)
OH MI WI NM = 52 (273)
OH MI WI NM NH = 56 (277)
OH MI WI NH = 51 (272)
OH MI CO IA = 53 (274)
OH MI CO IA NV = 58 (279)
OH MI CO IA NV NM = 63 (284)
OH MI CO IA NV NM NH = 67 (288)
OH MI CO IA NV NH = 62 (283)
OH MI CO IA NM = 58 (279)
OH MI CO IA NM NH = 62 (283)
OH MI CO IA NH = 57 (278)
OH MI CO NV = 51 (272)
OH MI CO NV NM = 56 (277)
OH MI CO NV NM NH = 60 (281)
OH MI CO NV NH = 55 (276)
OH MI CO NM = 51 (272)
OH MI CO NM NH = 55 (276)
OH MI CO NH = 50 (271)
OH MI IA NV = 49 (270)
OH MI IA NV NM = 54 (275)
OH MI IA NV NM NH = 58 (279)
OH MI IA NV NH = 53 (274)
OH MI IA NM = 49 (270)
OH MI IA NM NH = 53 (274)
OH MI NV NM NH = 51 (272)
OH VA MO WI = 54 (275)
OH VA MO WI CO = 63 (284)
OH VA MO WI CO IA = 70 (291)
OH VA MO WI CO IA NV = 75 (296)
OH VA MO WI CO IA NV NM = 80 (301)
OH VA MO WI CO IA NV NM NH = 84 (305)
OH VA MO WI CO IA NV NH = 79 (300)
OH VA MO WI CO IA NM = 75 (296)
OH VA MO WI CO IA NM NH = 79 (300)
OH VA MO WI CO IA NH = 74 (295)
OH VA MO WI CO NV = 68 (289)
OH VA MO WI CO NV NM = 73 (294)
OH VA MO WI CO NV NM NH = 77 (298)
OH VA MO WI CO NV NH = 72 (293)
OH VA MO WI CO NM = 68 (289)
OH VA MO WI CO NM NH = 72 (293)
OH VA MO WI CO NH = 67 (288)
OH VA MO WI IA = 61 (282)
OH VA MO WI IA NV = 66 (287)
OH VA MO WI IA NV NM = 71 (292)
OH VA MO WI IA NV NM NH = 75 (296)
OH VA MO WI IA NV NH = 70 (291)
OH VA MO WI IA NM = 66 (287)
OH VA MO WI IA NM NH = 70 (291)
OH VA MO WI IA NH = 65 (286)
OH VA MO WI NV = 59 (280)
OH VA MO WI NV NM = 64 (285)
OH VA MO WI NV NM NH = 68 (289)
OH VA MO WI NV NH = 63 (284)
OH VA MO WI NM = 59 (280)
OH VA MO WI NM NH = 63 (284)
OH VA MO WI NH = 58 (279)
OH VA MO CO = 53 (274)
OH VA MO CO IA = 60 (281)
OH VA MO CO IA NV = 65 (286)
OH VA MO CO IA NV NM = 70 (291)
OH VA MO CO IA NV NM NH = 74 (295)
OH VA MO CO IA NV NH = 69 (290)
OH VA MO CO IA NM = 65 (286)
OH VA MO CO IA NM NH = 69 (290)
OH VA MO CO IA NH = 64 (285)
OH VA MO CO NV = 58 (279)
OH VA MO CO NV NM = 63 (284)
OH VA MO CO NV NM NH = 67 (288)
OH VA MO CO NV NH = 62 (283)
OH VA MO CO NM = 58 (279)
OH VA MO CO NM NH = 62 (283)
OH VA MO CO NH = 57 (278)
OH VA MO IA = 51 (272)
OH VA MO IA NV = 56 (277)
OH VA MO IA NV NM = 61 (282)
OH VA MO IA NV NM NH = 65 (286)
OH VA MO IA NV NH = 60 (281)
OH VA MO IA NM = 56 (277)
OH VA MO IA NM NH = 60 (281)
OH VA MO IA NH = 55 (276)
OH VA MO NV = 49 (270)
OH VA MO NV NM = 54 (275)
OH VA MO NV NM NH = 58 (279)
OH VA MO NV NH = 53 (274)
OH VA MO NM = 49 (270)
OH VA MO NM NH = 53 (274)
OH VA WI CO = 52 (273)
OH VA WI CO IA = 59 (280)
OH VA WI CO IA NV = 64 (285)
OH VA WI CO IA NV NM = 69 (290)
OH VA WI CO IA NV NM NH = 73 (294)
OH VA WI CO IA NV NH = 68 (289)
OH VA WI CO IA NM = 64 (285)
OH VA WI CO IA NM NH = 68 (289)
OH VA WI CO IA NH = 63 (284)
OH VA WI CO NV = 57 (278)
OH VA WI CO NV NM = 62 (283)
OH VA WI CO NV NM NH = 66 (287)
OH VA WI CO NV NH = 61 (282)
OH VA WI CO NM = 57 (278)
OH VA WI CO NM NH = 61 (282)
OH VA WI CO NH = 56 (277)
OH VA WI IA = 50 (271)
OH VA WI IA NV = 55 (276)
OH VA WI IA NV NM = 60 (281)
OH VA WI IA NV NM NH = 64 (285)
OH VA WI IA NV NH = 59 (280)
OH VA WI IA NM = 55 (276)
OH VA WI IA NM NH = 59 (280)
OH VA WI IA NH = 54 (275)
OH VA WI NV NM = 53 (274)
OH VA WI NV NM NH = 57 (278)
OH VA WI NV NH = 52 (273)
OH VA WI NM NH = 52 (273)
OH VA CO IA = 49 (270)
OH VA CO IA NV = 54 (275)
OH VA CO IA NV NM = 59 (280)
OH VA CO IA NV NM NH = 63 (284)
OH VA CO IA NV NH = 58 (279)
OH VA CO IA NM = 54 (275)
OH VA CO IA NM NH = 58 (279)
OH VA CO IA NH = 53 (274)
OH VA CO NV NM = 52 (273)
OH VA CO NV NM NH = 56 (277)
OH VA CO NV NH = 51 (272)
OH VA CO NM NH = 51 (272)
OH VA IA NV NM = 50 (271)
OH VA IA NV NM NH = 54 (275)
OH VA IA NV NH = 49 (270)
OH VA IA NM NH = 49 (270)
OH MO WI CO = 50 (271)
OH MO WI CO IA = 57 (278)
OH MO WI CO IA NV = 62 (283)
OH MO WI CO IA NV NM = 67 (288)
OH MO WI CO IA NV NM NH = 71 (292)
OH MO WI CO IA NV NH = 66 (287)
OH MO WI CO IA NM = 62 (283)
OH MO WI CO IA NM NH = 66 (287)
OH MO WI CO IA NH = 61 (282)
OH MO WI CO NV = 55 (276)
OH MO WI CO NV NM = 60 (281)
OH MO WI CO NV NM NH = 64 (285)
OH MO WI CO NV NH = 59 (280)
OH MO WI CO NM = 55 (276)
OH MO WI CO NM NH = 59 (280)
OH MO WI CO NH = 54 (275)
OH MO WI IA NV = 53 (274)
OH MO WI IA NV NM = 58 (279)
OH MO WI IA NV NM NH = 62 (283)
OH MO WI IA NV NH = 57 (278)
OH MO WI IA NM = 53 (274)
OH MO WI IA NM NH = 57 (278)
OH MO WI IA NH = 52 (273)
OH MO WI NV NM = 51 (272)
OH MO WI NV NM NH = 55 (276)
OH MO WI NV NH = 50 (271)
OH MO WI NM NH = 50 (271)
OH MO CO IA NV = 52 (273)
OH MO CO IA NV NM = 57 (278)
OH MO CO IA NV NM NH = 61 (282)
OH MO CO IA NV NH = 56 (277)
OH MO CO IA NM = 52 (273)
OH MO CO IA NM NH = 56 (277)
OH MO CO IA NH = 51 (272)
OH MO CO NV NM = 50 (271)
OH MO CO NV NM NH = 54 (275)
OH MO CO NV NH = 49 (270)
OH MO CO NM NH = 49 (270)
OH MO IA NV NM NH = 52 (273)
OH WI CO IA NV = 51 (272)
OH WI CO IA NV NM = 56 (277)
OH WI CO IA NV NM NH = 60 (281)
OH WI CO IA NV NH = 55 (276)
OH WI CO IA NM = 51 (272)
OH WI CO IA NM NH = 55 (276)
OH WI CO IA NH = 50 (271)
OH WI CO NV NM = 49 (270)
OH WI CO NV NM NH = 53 (274)
OH WI IA NV NM NH = 51 (272)
OH CO IA NV NM NH = 50 (271)
MI VA MO WI = 51 (272)
MI VA MO WI CO = 60 (281)
MI VA MO WI CO IA = 67 (288)
MI VA MO WI CO IA NV = 72 (293)
MI VA MO WI CO IA NV NM = 77 (298)
MI VA MO WI CO IA NV NM NH = 81 (302)
MI VA MO WI CO IA NV NH = 76 (297)
MI VA MO WI CO IA NM = 72 (293)
MI VA MO WI CO IA NM NH = 76 (297)
MI VA MO WI CO IA NH = 71 (292)
MI VA MO WI CO NV = 65 (286)
MI VA MO WI CO NV NM = 70 (291)
MI VA MO WI CO NV NM NH = 74 (295)
MI VA MO WI CO NV NH = 69 (290)
MI VA MO WI CO NM = 65 (286)
MI VA MO WI CO NM NH = 69 (290)
MI VA MO WI CO NH = 64 (285)
MI VA MO WI IA = 58 (279)
MI VA MO WI IA NV = 63 (284)
MI VA MO WI IA NV NM = 68 (289)
MI VA MO WI IA NV NM NH = 72 (293)
MI VA MO WI IA NV NH = 67 (288)
MI VA MO WI IA NM = 63 (284)
MI VA MO WI IA NM NH = 67 (288)
MI VA MO WI IA NH = 62 (283)
MI VA MO WI NV = 56 (277)
MI VA MO WI NV NM = 61 (282)
MI VA MO WI NV NM NH = 65 (286)
MI VA MO WI NV NH = 60 (281)
MI VA MO WI NM = 56 (277)
MI VA MO WI NM NH = 60 (281)
MI VA MO WI NH = 55 (276)
MI VA MO CO = 50 (271)
MI VA MO CO IA = 57 (278)
MI VA MO CO IA NV = 62 (283)
MI VA MO CO IA NV NM = 67 (288)
MI VA MO CO IA NV NM NH = 71 (292)
MI VA MO CO IA NV NH = 66 (287)
MI VA MO CO IA NM = 62 (283)
MI VA MO CO IA NM NH = 66 (287)
MI VA MO CO IA NH = 61 (282)
MI VA MO CO NV = 55 (276)
MI VA MO CO NV NM = 60 (281)
MI VA MO CO NV NM NH = 64 (285)
MI VA MO CO NV NH = 59 (280)
MI VA MO CO NM = 55 (276)
MI VA MO CO NM NH = 59 (280)
MI VA MO CO NH = 54 (275)
MI VA MO IA NV = 53 (274)
MI VA MO IA NV NM = 58 (279)
MI VA MO IA NV NM NH = 62 (283)
MI VA MO IA NV NH = 57 (278)
MI VA MO IA NM = 53 (274)
MI VA MO IA NM NH = 57 (278)
MI VA MO IA NH = 52 (273)
MI VA MO NV NM = 51 (272)
MI VA MO NV NM NH = 55 (276)
MI VA MO NV NH = 50 (271)
MI VA MO NM NH = 50 (271)
MI VA WI CO = 49 (270)
MI VA WI CO IA = 56 (277)
MI VA WI CO IA NV = 61 (282)
MI VA WI CO IA NV NM = 66 (287)
MI VA WI CO IA NV NM NH = 70 (291)
MI VA WI CO IA NV NH = 65 (286)
MI VA WI CO IA NM = 61 (282)
MI VA WI CO IA NM NH = 65 (286)
MI VA WI CO IA NH = 60 (281)
MI VA WI CO NV = 54 (275)
MI VA WI CO NV NM = 59 (280)
MI VA WI CO NV NM NH = 63 (284)
MI VA WI CO NV NH = 58 (279)
MI VA WI CO NM = 54 (275)
MI VA WI CO NM NH = 58 (279)
MI VA WI CO NH = 53 (274)
MI VA WI IA NV = 52 (273)
MI VA WI IA NV NM = 57 (278)
MI VA WI IA NV NM NH = 61 (282)
MI VA WI IA NV NH = 56 (277)
MI VA WI IA NM = 52 (273)
MI VA WI IA NM NH = 56 (277)
MI VA WI IA NH = 51 (272)
MI VA WI NV NM = 50 (271)
MI VA WI NV NM NH = 54 (275)
MI VA WI NV NH = 49 (270)
MI VA WI NM NH = 49 (270)
MI VA CO IA NV = 51 (272)
MI VA CO IA NV NM = 56 (277)
MI VA CO IA NV NM NH = 60 (281)
MI VA CO IA NV NH = 55 (276)
MI VA CO IA NM = 51 (272)
MI VA CO IA NM NH = 55 (276)
MI VA CO IA NH = 50 (271)
MI VA CO NV NM = 49 (270)
MI VA CO NV NM NH = 53 (274)
MI VA IA NV NM NH = 51 (272)
MI MO WI CO IA = 54 (275)
MI MO WI CO IA NV = 59 (280)
MI MO WI CO IA NV NM = 64 (285)
MI MO WI CO IA NV NM NH = 68 (289)
MI MO WI CO IA NV NH = 63 (284)
MI MO WI CO IA NM = 59 (280)
MI MO WI CO IA NM NH = 63 (284)
MI MO WI CO IA NH = 58 (279)
MI MO WI CO NV = 52 (273)
MI MO WI CO NV NM = 57 (278)
MI MO WI CO NV NM NH = 61 (282)
MI MO WI CO NV NH = 56 (277)
MI MO WI CO NM = 52 (273)
MI MO WI CO NM NH = 56 (277)
MI MO WI CO NH = 51 (272)
MI MO WI IA NV = 50 (271)
MI MO WI IA NV NM = 55 (276)
MI MO WI IA NV NM NH = 59 (280)
MI MO WI IA NV NH = 54 (275)
MI MO WI IA NM = 50 (271)
MI MO WI IA NM NH = 54 (275)
MI MO WI IA NH = 49 (270)
MI MO WI NV NM NH = 52 (273)
MI MO CO IA NV = 49 (270)
MI MO CO IA NV NM = 54 (275)
MI MO CO IA NV NM NH = 58 (279)
MI MO CO IA NV NH = 53 (274)
MI MO CO IA NM = 49 (270)
MI MO CO IA NM NH = 53 (274)
MI MO CO NV NM NH = 51 (272)
MI MO IA NV NM NH = 49 (270)
MI WI CO IA NV NM = 53 (274)
MI WI CO IA NV NM NH = 57 (278)
MI WI CO IA NV NH = 52 (273)
MI WI CO IA NM NH = 52 (273)
MI WI CO NV NM NH = 50 (271)
VA MO WI CO IA = 50 (271)
VA MO WI CO IA NV = 55 (276)
VA MO WI CO IA NV NM = 60 (281)
VA MO WI CO IA NV NM NH = 64 (285)
VA MO WI CO IA NV NH = 59 (280)
VA MO WI CO IA NM = 55 (276)
VA MO WI CO IA NM NH = 59 (280)
VA MO WI CO IA NH = 54 (275)
VA MO WI CO NV NM = 53 (274)
VA MO WI CO NV NM NH = 57 (278)
VA MO WI CO NV NH = 52 (273)
VA MO WI CO NM NH = 52 (273)
VA MO WI IA NV NM = 51 (272)
VA MO WI IA NV NM NH = 55 (276)
VA MO WI IA NV NH = 50 (271)
VA MO WI IA NM NH = 50 (271)
VA MO CO IA NV NM = 50 (271)
VA MO CO IA NV NM NH = 54 (275)
VA MO CO IA NV NH = 49 (270)
VA MO CO IA NM NH = 49 (270)
VA WI CO IA NV NM = 49 (270)
VA WI CO IA NV NM NH = 53 (274)
MO WI CO IA NV NM NH = 51 (272)
555 solutions
P.S.
OH MI VA MO WI CO IA NV NM NH = 101 (322)
Wouldn't it be sweet.
Answer: 115 unique ways
unique solutions to
270: 38
271: 39
272: 38
ruby script to solve problem:
#! /usr/bin/env ruby
@votes = [55,34,31,27,21,21,20,17,15,15,15,13,12,11,11,11,11,10,10,10,10,9,9,9,8,8,7,7,7,7,6,6,6,5,5,5,5,5,4,4,4,4,4,3,3,3,3,3,3,3,3]
@results = Array.new(273, 0)
@results[0] = 1
@votes.each_index { |i|
272.downto(0) do |j|
if (@results[j] > 0)
newTotal = @votes[i] +j
if (newTotal <= 272)
@results[newTotal]+=1
end
end
end
}
puts @results[270]
puts @results[271]
puts @results[272]
Answer: 115 unique ways
Sigh. You might try reading some of the other comments before posting.
unique solutions to
270: 38
271: 39
272: 38
Uh, no. In fact,
270: 17054665123395
271: 17046339123934
272: 17032469851307
273: 64077397366
274: 1856215791
275: 49806934
276: 5308169
277: 239471
278: 46351
279: 3568
280: 78
281: 3
P.S. those 3 281's come from
55 34 31 27 21 21 20 17 15 15 13 12
There are three such combinations, for the three different pairs taken from GA, NC, and NJ, each with 15 EVs. Why someone would think that the totals can only be 270, 271, or 272 is beyond me.
dont know if this has been covered before, but is more likely than others. obama holds all kerry states accept hew hampshire, but wins iowa, colorado, and new mexico (currently leads in all 3) this would be 269, but if he picks up one electoral vote from splitting nebraska (winning the omaha district) that would be exactly 270.
Wow, I must say that I am completely turned off by jqb's condescending, smug attitude. What originally was a fun thought problem for a group to tackle has turned into a snarky comment laden page of trying to prove one's own intelligence and insult that of others. jqb, you may think that you're pretty smart, but that sort of attitude simply isn't respectful, and it certainly won't earn you respect. No need to comment back or argue with me, jqb, as I'm just going to just leave it at that and have lost interest in this thread.
Wow, I must say that I am completely turned off by jqb's condescending, smug attitude. What originally was a fun thought problem for a group to tackle has turned into a snarky comment laden page of trying to prove one's own intelligence and insult that of others.
Look on the bright side: At least he's not a biochemist. NEVER piss off one of them.
Wow, I must say that I am completely turned off by jqb's condescending, smug attitude. What originally was a fun thought problem for a group to tackle has turned into a snarky comment laden page of trying to prove one's own intelligence and insult that of others. jqb, you may think that you're pretty smart, but that sort of attitude simply isn't respectful, and it certainly won't earn you respect. No need to comment back or argue with me, jqb, as I'm just going to just leave it at that and have lost interest in this thread.
What a pathetic little crybaby. You're as bad as all those women who are going to vote for McCain because their feelings are hurt. The fact is that you're totally off base and are projecting, because comments of mine, like "Sorry to have been so dense, and so sloppy that I didn't even notice how absurd the results were" is not condescending or smug in any honest person's book.
P.S. I've been on the 'net for nearly 40 years (I was at UCLA when they installed the IMP) and have seen plenty of these emotionally immature people go all ad hominem, getting into whines about people's "tone" and and complaining about being condescended to (fragile ego much?), but I think this is the thinnest and least justified case I've ever seen. Perhaps Mike is just upset that his program is still running, and will be, for days -- it's an empirical fact, and kicking and screaming at the messenger won't change it.
In case anyone might have a use for it, here's my latest version of my program, cleaned up, commented, and sped up with the great pruning condition that Mike He mentioned:
#include <stdio.h>
#include <stdlib.h>
typedef unsigned long long Big;
typedef unsigned int Idx;
typedef unsigned int Votes;
typedef enum {
US, // states we will win
THEM, // states they will win
PLAY // states either might win
} Type;
typedef struct {
char const* name;
Votes v;
Type type;
} State;
static Idx n_of[3]; // number of states of type t
static Votes v_of[3]; // number of votes for states of type t
static State states[] = {
{"AL", 9, THEM}, {"AK", 3, THEM}, {"AR", 10, THEM}, {"AZ", 6, THEM},
{"CA", 55, US}, {"CO", 9, PLAY}, {"CT", 7, US}, {"DE", 3, US},
{"DC", 3, US}, {"FL", 27, THEM}, {"GA", 15, THEM}, {"HI", 4, US},
{"ID", 4, THEM}, {"IL", 21, US}, {"IN", 11, THEM}, {"IA", 7, PLAY},
{"KS", 6, THEM}, {"KY", 8, THEM}, {"LA", 9, THEM}, {"ME", 4, US},
{"MD", 10, US}, {"MA", 12, US}, {"MI", 17, PLAY}, {"MN", 10, US},
{"MS", 6, THEM}, {"MO", 11, PLAY}, {"MT", 3, THEM}, {"NE", 5, THEM},
{"NV", 5, PLAY}, {"NH", 4, PLAY}, {"NJ", 15, US}, {"NM", 5, PLAY},
{"NY", 31, US}, {"NC", 15, THEM}, {"ND", 3, THEM}, {"OH", 20, PLAY},
{"OK", 7, THEM}, {"OR", 7, US}, {"PA", 21, US}, {"RI", 4, US},
{"SC", 8, THEM}, {"SD", 3, THEM}, {"TN", 11, THEM}, {"TX", 34, THEM},
{"UT", 5, THEM}, {"VT", 3, US}, {"VA", 13, PLAY}, {"WA", 11, US},
{"WV", 5, THEM}, {"WI", 10, PLAY}, {"WY", 3, THEM}
};
#define NSTATES (sizeof(states)/sizeof(*states))
static Votes needed = 0; // # of votes needed to win
static Votes vsol = 0; // # of votes in sol
static Big nsol = 0; // # of solutions
static Idx sol[NSTATES]; // solution: indices into states
// find all of the solutions that consist of the states in sol[0..n-1]
// plus states from states[p..n_of[PLAY]-1];
// margin is # of votes available - needed
static void solve(Idx n, Idx p, int margin)
{
if( vsol >= needed ){
for( Idx i = 0; i < n; i++ )
printf("%s ", states[sol[i]].name);
printf("= %u (%u)\n", vsol, v_of[US] + vsol);
nsol++;
return;
}
// add each of p..n_of[PLAY]-1 in turn to sol
while( p < n_of[PLAY] && margin >= 0 ){
Votes v = states[sol[n] = p++].v;
vsol += v;
solve(n+1, p, margin);
vsol -= v;
margin -= v; // votes of sol[n] are no longer available
}
}
// print states of type t
static void prstates(char const* s, Type t)
{
printf("%d %s:", n_of[t], s);
for( Idx i = 0; i < NSTATES; i++ )
if( states[i].type == t )
printf(" %s", states[i].name);
printf(" = %u", v_of[t]);
if( t == US ) printf(", %u more needed", needed);
printf("\n");
}
// put PLAY states before non-PLAY states;
// order PLAY states by descending vote count
static int cmp(void const* a, void const* b)
{
State* x = (State*)a;
State* y = (State*)b;
return(x->type == PLAY
? (y->type == PLAY
? (int)(y->v - x->v)
: -1)
: (y->type == PLAY
? 1
: 0));
}
int main(void)
{
for( Idx i = 0; i < NSTATES; i++ ){
Type t = states[i].type;
n_of[t]++;
v_of[t] += states[i].v;
needed += states[i].v;
}
needed = needed/2 + 1 - v_of[US];
prstates("safe", US);
prstates("out of reach", THEM);
prstates("in play", PLAY);
qsort(states, NSTATES, sizeof *states, cmp);
solve(0, 0, v_of[PLAY] - needed);
printf("%llu solutions\n", nsol);
return 0;
}
jqb, if you've been on the Internet since Al Gore invented it, then you ought to know by now that a sense of humor helps. Hey, it's only a movie. Now put down the beaker, and step back from the ledge ...
jqb, if you've been on the Internet since Al Gore invented it
I worked with Vint Cerf at UCLA -- you know, the co-inventor of TCP/IP -- who, together with the other co-inventor, co-inventor, Bob Kahn, that Al Gore's statements about his role in the creation of the internet were accurate, and that the the commercial internet would have been much longer in coming if not for Gore's efforts. So don't go propagating that lie, even in jest.
then you ought to know by now that a sense of humor helps.
Tell it to Mike He.
Hey, it's only a movie. Now put down the beaker, and step back from the ledge ...
Fuck off, you pompous ass. :-)
together with the other co-inventor, co-inventor, Bob Kahn, that Al Gore's statements
Make that "together with the other co-inventor, Bob Kahn, wrote that ..."
Specifically:
http://www.theregister.co.uk/2000/10/02/net_builders_kahn_cerf_recognise/
"""
Al Gore and the Internet
By Robert Kahn and Vinton Cerf
Al Gore was the first political leader to recognize the importance of the Internet and to promote and support its development.
No one person or even small group of persons exclusively "invented" the Internet. It is the result of many years of ongoing collaboration among people in government and the university community. But as the two people who designed the basic architecture and the core protocols that make the Internet work, we would like to acknowledge VP Gore's contributions as a Congressman, Senator and as Vice President. No other elected official, to our knowledge, has made a greater contribution over a longer period of time.
Last year the Vice President made a straightforward statement on his role. He said: "During my service in the United States Congress I took the initiative in creating the Internet." We don't think, as some people have argued, that Gore intended to claim he "invented" the Internet. Moreover, there is no question in our minds that while serving as Senator, Gore's initiatives had a significant and beneficial effect on the still-evolving Internet. The fact of the matter is that Gore was talking about and promoting the Internet long before most people were listening. We feel it is timely to offer our perspective.
As far back as the 1970s Congressman Gore promoted the idea of high speed telecommunications as an engine for both economic growth and the improvement of our educational system. He was the first elected official to grasp the potential of computer communications to have a broader impact than just improving the conduct of science and scholarship. Though easily forgotten now, at the time this was an unproven and controversial concept. Our work on the Internet started in 1973 and was based on even earlier work that took place in the mid-late 1960s. But the Internet, as we know it today, was not deployed until 1983. When the Internet was still in the early stages of its deployment, Congressman Gore provided intellectual leadership by helping create the vision of the potential benefits of high speed computing and communication. As an example, he sponsored hearings on how advanced technologies might be put to use in areas like coordinating the response of government agencies to natural disasters and other crises.
As a Senator in the 1980s Gore urged government agencies to consolidate what at the time were several dozen different and unconnected networks into an "Interagency Network." Working in a bi-partisan manner with officials in Ronald Reagan and George Bush's administrations, Gore secured the passage of the High Performance Computing and Communications Act in 1991. This "Gore Act" supported the National Research and Education Network (NREN) initiative that became one of the major vehicles for the spread of the Internet beyond the field of computer science.
...
"""
jqb, you're more fun than a barrel of monkeys. Of course, there is no such thing as a barrel of monkeys, so I'd better stop lying about that, too.
Charles Pluckhahn said...
* PLONK *
For those interested, here is an implementation in LISP.
Takes 80 ms to find the correct number (51199463116367)
(defvar *ev-count* (make-array '(60 300)))
(defvar *evs* (list 9 3 10 6 55 9 7 3 3 27 15 4 4
21 11 7 6 8 9 4 10 12 17 10 6 11 3
5 5 4 15 5 31 15 3 20 7 7 21 4 8 3
11 34 5 3 13 11 5 10 3
))
(defun init-ev-count ()
(setq *ev-count* (make-array '(60 300))))
(defun ev-count (ev-list total)
(cond ((> total (apply #'+ ev-list))
0)
((< total 0)
0)
((= total 0)
1)
((aref *ev-count* (length ev-list) total))
(t (setf (aref *ev-count* (length ev-list) total)
(+ (ev-count (cdr ev-list) total)
(ev-count (cdr ev-list) (- total (car ev-list))))))))
(defun ev-count-unique (ev-list total min-ev)
(init-ev-count)
(let ((sufficient-evs (remove-if #'(lambda (ev) (< ev min-ev))
ev-list)))
(ev-count sufficient-evs total)))
(defun ev-count-total (ev-list total)
(loop for ev-min from 1 to 55
sum (ev-count-unique ev-list (+ (1- total) ev-min) ev-min)))
jqb, it's okay if you like plonk -- after all, we ARE Democrats -- but I prefer the good stuff. Salut!
Just for the record, I saw a barrel of monkeys once.
One time I drank so much plonk that I saw God. Or was it absinthe that I drank? Hmm. I don't really remember. And was it God or a monkey? And ...
If we first add the states with the most EVs (from the top down) we get 271 with the top 11 (so that's one). This means we need strictly more than 10 (this eliminates and partition of 10 or less states automatically).
Next we start at the bottom and reach 270+ with 41 so ANY partition of 41 or more will win. That's (51 choose 41 + 51 choose 42 + etc..) 16,593,192,942 different partitions according to the Google calculator.
I found some maple code (matlab would be better but this was lying around and I have free access to a cluster at work anyway) that will enumerate subsets. If it runs as fast as the author claims I should be able to simply make the computer(s) enumerate subsets (in the 12-40 range), add up each and print only those that add to 270+. This is really dirty but noone said anything about efficiently finding a solution :)
情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣用品,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,情趣,美國aneros,rudeboy,英國rudeboy,英國Rocksoff,德國Fun Factory,Fun Factory,英國甜筒造型按摩座,甜筒造型按摩座,英國Rock Chic ,瑞典 Lelo ,英國Emotional Bliss,英國 E.B,荷蘭 Natural Contours,荷蘭 N C,美國 OhMiBod,美國 OMB,Naughti Nano ,音樂按摩棒,ipod按摩棒,美國 The Screaming O,美國TSO,美國TOPCO,美國Doc Johnson,美國CA Exotic,美國CEN,,矽膠按摩棒,猛男倒模,真人倒模,仿真倒模,PJUR,Zestra,適趣液,穿戴套具,日本NPG,雙頭龍,FANCARNAL,日本NIPPORI,日本GEL,日本Aqua Style,美國WET,費洛蒙,費洛蒙香水,仿真名器,av女優,打炮,做愛,性愛,口交,吹喇叭,肛交,成人用品網,情趣用品討論,成人購物網,鎖精套,鎖精環,持久環,持久套,拉珠,逼真按摩棒,名器,超名器,逼真老二,電動自慰,自慰,打手槍,仿真女郎,SM道具,SM,性感內褲,仿真按摩棒,pornograph,hunter系列,h動畫,成人動畫,成人卡通,近親相姦,顏射,盜攝,偷拍,本土自拍,素人自拍,公園露出,街道露出,野外露出,誘姦,迷姦,輪姦,凌辱,痴漢,痴女,素人娘,中出,巨乳,調教,潮吹,av,a片,成人影片,成人影音,線上影片,色情影音,色情光碟,線上A片,免費A片,A片下載,成人電影,色情電影,TOKYO HOT,SKY ANGEL,一本道,SOD,S1,ALICE JAPAN,皇冠系列,老虎系列,東京熱,亞熱,武士系列,新潮館,情趣用品,情趣,情趣商品,情趣網站,跳蛋,按摩棒,充氣娃娃,自慰套,G點,性感內衣,情趣內衣,角色扮演,生日禮物,生日精品,自慰,打手槍,潮吹,高潮,後庭,情色論譠,影片下載,遊戲下載,手機鈴聲,音樂下載,開獎號碼,統一發票號碼,夜市,統一發票對獎,保險套,做愛,減肥,美容,瘦身,當舖,軟體下載,汽車,機車,手機,來電答鈴,週年慶,美食,徵信社,網頁設計,網站設計,室內設計,靈異照片,同志,聊天室,運動彩券,大樂透,威力彩,搬家公司,除蟲,偷拍,自拍,無名破解,av女優,小說,民宿,大樂透開獎號碼,大樂透中獎號碼,威力彩開獎號碼,討論區,痴漢,懷孕,美女交友,交友,日本av,日本,機票,香水,股市,股市行情, 股市分析,租房子,成人影片,免費影片,醫學美容,免費算命,算命,姓名配對,姓名學,姓名學免費,遊戲,好玩遊戲,好玩遊戲區,線上遊戲,新遊戲,漫畫,線上漫畫,動畫,成人圖片,桌布,桌布下載,電視節目表,線上電視,線上a片,線上掃毒,線上翻譯,購物車,身分證製造機,身分證產生器,手機,二手車,中古車,法拍屋,歌詞,音樂,音樂網,火車,房屋,情趣用品,情趣,情趣商品,情趣網站,跳蛋,按摩棒,充氣娃娃,自慰套, G點,性感內衣,情趣內衣,角色扮演,生日禮物,精品,禮品,自慰,打手槍,潮吹,高潮,後庭,情色論譠,影片下載,遊戲下載,手機鈴聲,音樂下載,開獎號碼,統一發票,夜市,保險套,做愛,減肥,美容,瘦身,當舖,軟體下載,汽車,機車,手機,來電答鈴,週年慶,美食,徵信社,網頁設計,網站設計,室內設計,靈異照片,同志,聊天室,運動彩券,,大樂透,威力彩,搬家公司,除蟲,偷拍,自拍,無名破解, av女優,小說,民宿,大樂透開獎號碼,大樂透中獎號碼,威力彩開獎號碼,討論區,痴漢,懷孕,美女交友,交友,日本av ,日本,機票,香水,股市,股市行情,股市分析,租房子,成人影片,免費影片,醫學美容,免費算命,算命,姓名配對,姓名學,姓名學免費,遊戲,好玩遊戲,好玩遊戲區,線上遊戲,新遊戲,漫畫,線上漫畫,動畫,成人圖片,桌布,桌布下載,電視節目表,線上電視,線上a片,線上a片,線上翻譯,購物車,身分證製造機,身分證產生器,手機,二手車,中古車,法拍屋,歌詞,音樂,音樂網,借錢,房屋,街頭籃球,找工作,旅行社,六合彩,整型論壇,整型論壇,珠海,雷射溶脂,婚紗,網頁設計,水噹噹論壇,台中隆鼻,果凍隆乳,改運整型,自體脂肪移植,新娘造型,婚禮顧問,下川島,常平,常平,珠海,澳門機票,香港機票,貸款,貸款,信用貸款,宜蘭民宿,花蓮民宿,未婚聯誼,網路購物,婚友,婚友社,未婚聯誼,交友,婚友,婚友社,單身聯誼,未婚聯誼,未婚聯誼, 婚友社,婚友,婚友社,單身聯誼,婚友,未婚聯誼,婚友社,未婚聯誼,單身聯誼,單身聯誼,白蟻,白蟻,除蟲,老鼠,減肥,減肥,在家工作,在家工作,婚友,單身聯誼,未婚聯誼,婚友,交友,交友,婚友社,婚友社,婚友社,大陸新娘,大陸新娘,越南新娘,越南新娘,外籍新娘,外籍新娘,台中坐月子中心,搬家公司,搬家公司,中和搬家,台北搬家,板橋搬家,新店搬家,線上客服,網頁設計,線上客服,網頁設計,植牙,關鍵字,關鍵字,seo,seo,網路排名,自然排序,網路排名軟體,交友,越南新娘,婚友社,外籍新娘,大陸新娘,越南新娘,交友,外籍新娘,視訊聊天,大陸新娘,婚友社,婚友,越南新娘,大陸新娘,越南新娘,視訊交友,外籍新娘,網路排名,網路排名軟體,網站排名優化大師,關鍵字排名大師,網站排名seo大師,關鍵字行銷專家,關鍵字,seo,關鍵字行銷,網頁排序,網頁排名,關鍵字大師,seo大,自然排名,網站排序,網路行銷創業,汽車借款,汽車借錢,汽車貸款,汽車貸款,拉皮,抽脂,近視雷射,隆乳,隆鼻,變性,雙眼皮,眼袋,牙齒,下巴,植牙,人工植牙,植髮,雷射美容,膠原蛋白,皮膚科,醫學美容,玻尿酸,肉毒桿菌,微晶瓷,電波拉皮,脈衝光,關鍵字,關鍵字,seo,seo,網路排名,自然排序,網路排名軟體,英語演講,托福,Toastmaster,
艾葳酒店經紀公司提供專業的酒店經紀, 酒店上班小姐,八大行業,酒店兼職,傳播妹,或者想要到打工兼差、打工,兼差,或者八大行業,酒店兼職,想去酒店上班, 日式酒店,制服酒店,ktv酒店,禮服店,整天穿得水水漂漂的,還是想去制服店當上班小姐,水水們如果想要擁有打工工作、晚上兼差工作、兼差打工、假日兼職、兼職工作、酒店兼差、兼差、打工兼差、日領工作、晚上兼差工作、酒店工作、酒店上班、酒店打工、兼職、兼差、兼差工作、酒店上班等,想了解酒店相關工作和特種行業內容,想兼職工作日領、假日兼職、兼差打工、或晚班兼職想擁有快速賺錢又有保障的工作嗎???又可以現領請找專業又有保障的艾葳酒店經紀公司!
艾葳酒店經紀是合法的公司工作環境高雅時尚，無業績壓力，無脫秀無喝酒壓力，高層次會員制客源，工作輕鬆，可日領、現領。
一般的酒店經紀只會在水水們第一次上班和領薪水時出現而已，對水水們的上班安全一點保障都沒有！艾葳酒店經紀公司的水水們上班時全程媽咪作陪，不需擔心！只提供最優質的酒店上班,酒店上班,酒店打工環境、上班條件給水水們。心動嗎!? 趕快來填寫你的酒店上班履歷表
水水們妳有缺現領、有兼職、缺錢卡奴的煩腦嗎?想到日本留學缺錢嗎?妳是傳播妹??想要擁有高時薪又輕鬆的夜間兼職工作,打工機會和,假日打工,假日兼職賺錢的機會嗎??想實現夢想卻又缺錢沒錢嗎!??
艾葳酒店台北酒店經紀招兵買馬!!徵專業的酒店打工,想要去酒店的水水,想要短期日領,酒店日領,禮服酒店,制服店,酒店經紀,ktv酒店,便服店,酒店工作,禮服店,酒店小姐,酒店經紀人,
等相關服務 幫您快速的實現您的夢想~!!
酒店經紀人,
菲梵酒店經紀,
酒店經紀,
禮服酒店上班,
酒店小姐兼職,
便服酒店經紀,
酒店打工經紀,
制服酒店工作,
專業酒店經紀,
合法酒店經紀,
酒店暑假打工,
酒店寒假打工,
酒店經紀人,
菲梵酒店經紀,
酒店經紀,
禮服酒店上班,
酒店經紀人,
菲梵酒店經紀,
酒店經紀,
禮服酒店上班,
酒店小姐兼職,
便服酒店工作,
酒店打工經紀,
制服酒店經紀,
專業酒店經紀,
合法酒店經紀,
酒店暑假打工,
酒店寒假打工,
酒店經紀人,
菲梵酒店經紀,
酒店經紀,
禮服酒店上班,
酒店小姐兼職,
便服酒店工作,
酒店打工經紀,
制服酒店經紀,
酒店經紀,
菲
梵,
Post a Comment