Let’s take a break from the presidential campaign to consider a recreational math question posed by New York Times correspondent Binyamin Appelbaum. On Twitter, he wondered:

Is there any number of electoral votes between 0 and 538 that is impossible to amass, assuming electors are faithful?

Put another way, could a presidential candidate win any number of electoral votes from 0 to 538?

The answer is intuitive if you know a key piece of electoral college trivia. But there’s still a fun question of how best to actually prove that intuition.

My best attempt below. Stop reading now if you want to figure it on your own.

Each state gets at least three electoral votes. Most states give all those votes to the winner of the state’s popular vote. So you might think that it isn’t possible for a candidate to get 1 vote, 2 votes, 536 votes, or 537 votes.

That would be true except that Maine and Nebraska allocate votes by congressional district (plus two for the state as a whole). Since Maine has 4 votes, it could provide 1 vote for a candidate.* With 5 votes, Nebraska could produce 1 or 2 votes for a candidate.

So 1, 2, 536, and 537 are possible.

What about the rest of the possibilities? Intuitively, it seems as though all the other numbers should be possible. But how best to prove it? Working through every number would be tedious.

Happily, there are ways to trim it down.

First, you don’t have to do all the cases. ItÂ suffices to get vote totals from 0 to 269. If those are possible, so are the rest. Why? Because in those cases, the candidate’s opponent gets between 0 and 269 votes. For a candidate to get 338 votes, for example, their opponent (or opponents) must get 200 votes.

That observation cuts the work in half.

Second, we can get any vote total up to 255 using a little binary reasoning. We can get 1 vote from a district in Maine; 2 from two districts in Nebraska; 4 from Rhode Island; 8 from Kentucky; 16 from Michigan; 32 by combining Illinois (20) and Washington (12); 64 by combining California (55) and Mississippi (9); and 128 by combining Texas (38), Florida (29), New York (29), Pennsylvania (20), Nevada (6), and Utah (6).

Those states can then be combined to create any vote total from 0 to 255. For example, 92 = 64 + 16 + 8 + 4 = California, Mississippi, Michigan, Kentucky, and Rhode Island.

Toss New Jersey (14) into the mix, and you can get any vote total up to 269. For example, you can get 264 by adding New Jersey to the group of “binary” states that total 250. QED.

Bottom line: Yes, a candidate can win anywhere from 0 to 538 electoral votes.

** Maine could yield 2 votes for a candidate in a three-way race. Also, an earlier version had a typo; Nebraska has 5 votes not 6.*

on November 3, 2012 at 10:29 amKimCute – fun with math.

on November 5, 2012 at 7:28 amLizHere was the logic I used: I knew that Maine and Nebraska could split there votes, so 1 and 2 were both possible. From there, I reasoned that if the gap between any two states’ electoral votes were no larger than the sum of the electoral votes for the states that have fewer votes, then all combinations of electoral vote totals adding to 538 must be possible. If you order the states by their electoral votes, the first gap is at 19 votes. The sum of all the electoral votes for states with fewer than 19 votes is 367. There are also gaps at 21-28 votes, 30-37 votes, and 39-54 votes. Obviously, for all of these, the sum of the total electoral votes of the states with fewer votes is larger than the gap, so every combination must be possible.

I think the binary reasoning proof is more elegant though.

on November 5, 2012 at 2:33 pmJustafedLate to the party, but I think two slight changes in the Liz proof makes it equally compelling, albeit maybe in a different way.

First, we make a list of *single* states or *single* combinations of states having an integral number of EVs up to 23. We find the first gap at row 17 (not 19), and we fill this “row” with, e.g., CO+LA (two states we have not used yet). The gap at 19 we will fill with MD + SC, the gap at 21 with MO + TN, The Gap at 22 with KS + UT + MN, and the gap at 23 with MI + OK (we used GA itself for row 16, of course). Note that the total of the electoral votes through single states or combinations *in our list* up through row 23 is 286. Now, we can trivially get a number of EVs totalling 1-23 by just pointing to the appropriate row in our list. We can then get a number of EVs totalling 24 by choosing the 23rd row and add the first row, get 25 by choosing rows 23 and 2, etc. all the way up to 45, which is just rows 23 and 22 added together. Then 46 is (wait for it…) row 23 plus row 22 plus row 1, and we can count in like fashion all the way up to 286, the total EVs in our list of states totalling EVs from 1 through 23. Because of symmetry, we only need to “cover” totals up to 269 with our scheme as OP notes, and we are done.

on November 5, 2012 at 5:52 pmDonald MarronNice. I guess one would call this the triangular number proof. Figure out lowest N so that N*(N+1)/2 > 269. That’s 23. As you say, then find distinct states or state combos for 1 through 23, making everything from 1 to N*(N+1)/2 is doable. Very nice.