Indistinguishable from Jesse

A presidential candidate could be elected with as a little as 21.8% of the popular vote by getting just over 50% of the votes in DC and each of 39 small states. This is true even when everyone votes and there are only two candidates. In other words, a candidate could lose with 78.2% of the popular vote by getting just under 50% in small states and 100% in large states.

The optimal set of states to take (the one that lets a candidate win with the smallest popular vote) is not the N states with the smallest population. It's also not the N states with the smallest value for (population/electors), which would be optimal if you could get exactly 270 electoral votes that way.

The optimal solution happens to get exactly 270 electoral votes. In this solution, the winner takes DC, the 37 smallest states, the 39th smallest state, and the 40th smallest state. (The winner takes Alabama, Alaska, Arizona, Arkansas, Colorado, Connecticut, Delaware, DC, Hawaii, Idaho, Indiana, Iowa, Kansas, Kentucky, Louisiana, Maine, Maryland, Minnesota, Mississippi, Missouri, Montana, Nebraska, Nevada, New Hampshire, New Mexico, North Carolina, North Dakota, Oklahoma, Oregon, Rhode Island, South Carolina, South Dakota, Tennessee, Utah, Vermont, Virginia, Washington, West Virginia, Wisconsin, and Wyoming.)

Read on for my assumptions and algorithm.

My copy of Garey and Johnson arrived the other day. I wonder if it will make good airplane reading while I'm heading to Mozilla Developer Day next week.

I bought a textbook, some paper, and some binders at Huntley Bookstore today. I asked the guy at checkout to put my purchase in two bags of roughly equal weight. He thought this was a strange request and expressed uncertainty about his solution, but the bags felt balanced as I walked back to my dorm.

Only later did I realize my grave mistake: I had casually asked him to solve an NP-complete problem.