Counting with Polynomials

Here is a little counting problem I just came across that makes me glad to live in the age of computer algebra systems. You already know that there are 538 electoral votes distributed among the fifty states, and probably also know that it takes 270 of them to get elected. If you didn't know, you get them in clumps. Winning the state of Texas gives you 34 votes, winning Utah only nets 5. The number of votes for each state is here in case you want to try to solve the problem yourself.

The problem involves a mathematical idea we call a "critical coalition". The idea is to find enough states that could be grouped together (hence the coalition part) to add up to 270 or more, but only JUST enough. The critical part means your coalition is balanced so that if any state drops out, you do NOT have 270 or more votes. That's it, just make a list of everyway you could combine states to make a critical coalition; no fuss about political realities... just pure counting math. If you can handle that problem by ANY method, you can probably stop reading now because I have little to teach you. I'm bringing it up because I saw a really great solution Isabel Lugo who writes the blog "God Plays Dice", which is very worth reading.(and if you are doing the problem, I will give her numeric solution at the bottom so that you can check your work, or hers). If you are young and not used to a lot of variables, pick up a pencil, make lots of notes, read slowly, reread, struggle with it...it really is powerful stuff.

Isabel's solution was to multiply (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). Ok, this is only part of the solution, but when you multiply that big polynomial, what it will give you is the number of coallitions you can put together of EVERY size that includes at least one of the states with three electorial votes. This is a polynomial of degree 538, and it has encoded in the coefficients of the terms some of the numbers you need to answer the questions.

To try to make that understandable to my high school readers, here is a smaller, but similar problem. What are the critical coalitions of pools of 2, 2, 3, and 4? Those total to 11, and you need 6 to get a victory. I think you can figure this one out by hand, so let's do that first. The set 4+3 is a critical coalition, they add up to 6 or more, and if you take either of them away, it doesn't. Likewise 4+2 forms two coalitions, one with either 2. Another is found by 3+2+2, and I think that is all of them. So we have a total of four coalitions. Now doing this one with a polynomial is longer than doing it by hand, but it shows you how to get the answer by polynomials (with a computer's help of course).

To represent the solutions with a polynomial, we use (1+x^4) for the pool with four votes, (1+x^3) for the pool with three votes, and (1+x^2) for each of the pools with two votes. For a minute I will ignore the -1 at the end of one Isabel's solution, but fear not, we will bring it back in a few lines. When we multiply (1+x^4)(1+x^3)(1+x^2)^2 (the last is squred because there were two of them) we get x^11 + 2 x^9 + x^8 + 2 x^7 + 2x^6 + 2x^5 + 2x^4 + x^3 + 2x^2 + 1. So what?, you ask. If you look at the coefficients of each term (the numbers in front) you get the number of coalitions (not critical, just any old coalition) that can be formed that have as many votes as the power of x. For example, the 2 x^9 tells us that there are two coalitions that have 9 votes. We can see that would be 4+3+ 2 and 4+3+(the other )2. And what about 2 x^7? Well, we can have 4+3 for one coalition, and 3+2+2 for another. See how that works? Check the others to be sure I didn't mess up (and if I did, write a nice correction comment to help me out).

Now that doesn't answer the critical coalition question, but it is a great calculating tool. And if you are still trying to figure out how many eight letter words can be made using the letters in Mississippi that I asked in my recent blog, Yes, Barbie, Math is Hard, then the polynomial method described above should help.

But what about this problem? We can count all the coalitions, and even tell if they have a majority (2+2 is still a coalition, even 2 or 3 by itself is a considered a coalition, but they don't have a majority), but we can't figure out if it is critical or not. And that is where the -1 in the last term of Isabel's polynomial comes in; it allows us to eliminate all the coalitions that don't contain some solution. In our mini-problem, if we change the last term to (1+x^4)(1+x^3) ((1+x^2)^2 -1) we get a listing of all the coalitions that contain a 2. x^11 + 2 x^9 + x^8 + 2 x^7 + 2x^6 + 2x^5 + 2x^4 + x^3 + 2x^2 + 1 - ((1+x^4)(1+x^3)) . That leaves us x^11 + 2 x^9 + x^8 + 1 x^7 + 2x^6 + 2x^5 + 1x^4 + 2x^2. Now each of these coalitions have at least one member who had two votes, so we want to only count the ones that have a total of 6 or 7 since those are the only ones which would be critical. The two is the smallest member, so his absence would only impact the success of coalitions with 7 or less votes. Looking at the terms with powers of 6 and 7 we see that there are 3 such critical coalitions, (3 + 2 + 2; 4+2 and 4+ (other)2). Ok.. so what about coalitions that DON"T have a two... We just take the x^2 term completely out of the mix, and multiply again with -1 on the x^3 term.....(1+x^4)((1+x^3)-1) gives us x^7 + x^3. Since only the x^7 is a winning coalition, and it must be critical because if we took away the 3, the total is less than 6. And that is all of the winning coalittions, if we leave out all that have a 2 and a 3, we are left with 4, which will not win. Add the three that include a 2, and the one that does not, and you get all four coalitions. When Isable did that with her BIG equation, she came up with ...wait for it...51,199,463,116,367 ... that is how many different critical coalitions of states could be combined to get the 270 electoral votes needed to be elected President.

Ok, so now a practice problem for you.. suppose we had voting pools of 2, 3, 3, 5, and 7 for a total of 20.. that means 11 for a majority. Can you figure out how many critical coalitions there are.. if you want to submit a comment, we can walk you towards the answer with some hints and (if needed) corrections. Good luck.