In Fall 2018, I was taking a combinatorics course, and my final was coming up. My friend Marc tried to antagonize me by asking some dumb combo question he made up on the fly, and I ignored him. However, when we were talking the next day, he brought up the same question unironically; he was stumped.
For anybody who hasn’t watched Avengers: Infinity War, the premise is that a big purple man named Thanos wants to split the universe’s population in half. Marc’s question, dubbed “The Thanos Problem”, went something like this.
Thanos comes to Georgia Tech and wants to get rid of half of the students on campus. However, because Thanos wants everything perfectly balanced, the number of children in each class should also be halved. How many ways are there for Thanos to do this?
As a simplifying assumption, you can assume that every class has an even amount of students in it.
When I first heard the question, I thought it was trivial. If there were classes from to , with each representing the number of students in the class, you could just compute , where is the number of ways to pick kids from a class of size – this is known as a combination
However, I quickly realized that was totally incorrect; it only worked if you assumed no two classes had the same student in it, which is never the case unless everybody at your school only took one class a semester – maybe we could apply this approach to the students at UGA.
Spoilers Below
It can be super fun to try to think of a solution to this problem yourself, and reading the rest of this article will probably give away the solution (heck, the title of this blog post is already a pretty big hint). Also, there might be solutions better than mine out there, involving graphs or something, that you might discover on your own! You should try to figure out the problem yourself before you continue reading!
Spoiler as Promised
I sat and pondered for a long time, putting off studying for my combinatorics final to try and solve this problem. I tried graphs, inclusion-exclusion, and everything else I could think of. Eventually, I realized that I could solve this problem with multinomial coefficients, and I instantly wanted to share this problem and solution with the world! However, I’m sure lots of people don’t know how to count with multinomial coefficients – I didn’t really learn it until the end of this semester. This blog post will introduce the core concepts regarding counting with coefficients, and the next post will actually show you how to solve this problem!
Quick Number Theory
Let’s look at the following factored expression:
When multiplied out, we get this:
But where did the coefficients of in front of and come from? This may seem like a silly question – you just multiply each term in the first expression by each in the second and combine like-terms! But what do those values of mean?
If you think about it, the in front of means that there were different ways to form , and they were summed together to leave us with . We can see the two ways to form by looking at the factored form of the polynomials – the from the first polynomial times the in the second polynomial is one way, and the from the first polynomial multiplied by the in the second polynomial is the other.
What if I told you that calculating the coefficients of the product of polynomials (or more generally, multinomials) is one of the most powerful counting techniques out there?!
Consider the Following
Like any true patriot, let’s suppose we have red, white, and blue soda cans. We want to pick 10 soda cans subject to the following constraints
- We can only pick an even number of red cans
- We can pick 2, 3, or 4 white cans
- We can pick 0, 5, or 10 blue cans
We could count this out by hand, but that would be extremely tedious, and when somebody adds another type of can, we’ll have to do even more work. What if I told you we could solve this problem using polynomial coefficients?!
Let’s formulate the red cans as , the white cans as , and the blue cans as . Note that the power of each term corresponds to the number of cans we’re allowed.
If we take the product of these three multinomials, we get the following absolute unit of an exponential
Looking at the coefficient of , we see a value of . For any of you brave enough to try to solve this by hand, you will have (hopefully) gotten the same answer. Your valid options for getting cans are
- red, white, blue
- red, white, blue
- red, white, blue
Observe that , which is how we can represent the option of picking cans. One might think, “Hey, we can omit the because it’s cans and we don’t care about it”. That’s actually wrong! Imagine we did this with the following example and expressed the blue polynomial as . Once we multiply the red polynomial by the white to get the “pink” polynomial of , we would be unable to keep the term, because it would get multiplied by and from the blue polynomial. Our resulting answer would only have with a coefficient of , which results from multiplying the blue polynomial’s by the “pink” polynomial’s .
Now It’s Your Turn!
Let’s do a quick practice problem! Imagine you have 10 students in a class and you want to remove 5 of them.
What is the product of polynomials you would compute, and what coefficient would you look for? While you’re at it, why not just find the coefficient – you can plug your expression into mathematica or something to compute it.
It turns out, the number of ways to pick $$ n $$ kids out of your classroom of $$ 10 $$ is just $$ {10 \choose n} $$!
This may seem like a big coincidence, but it's actually just the binomial theorem at work! The reason the binomial theorem applies here (but not to the soda example above) is because $$ 1 + x $$ just has two terms; that's where binomial gets its "bi" from.
This primer on counting with coefficients should give you the necessary tools to solve the Thanos Problem – however, if you get stuck, I’ll be releasing another post shortly to walk through the solution step by step!