If you didn’t read the last post, “The Thanos Problem” is something my friend Marc came up with while trying to antagonize me before my combinatorics final. It goes 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.
In my opinion, the hardest part of this question is dealing with students who are in multiple classes. This means that, if you remove a student from one class to make the class size half its original size, and if that student is in another class that has already been balanced, that previously balanced class will now be a person short.
A (failed) Graph Based Approach
Skip to here if you don’t care about graphs.
When I first heard this problem, I thought I could formulate it as a graph problem – specifically, as a bipartite graph problem.
A bipartite graph has two “sets” of vertices. The constraint of a bipartite graph is that vertices may not have edges connecting themselves to vertices in their own set. This arrangement is nice for this problem, because you could have one “set” that represent students and another “set” representing courses. Edges between the two “sets” represent membership of a student in a given course. Because this graph is bipartite, there will be no nonsensical lines connecting students to other students or courses to other courses!
Let’s quickly introduce some other basic graph theory concepts. The first is the degree of a vertex. If a vertex is connected to other vertices, it has a degree of . Basically, the degree of a vertex is the number of edges that come out of that vertex. For our sake, we will ignore loops, which is where a vertex has an edge connecting itself to itself – bipartite graphs don’t have loops in the first place.
Now let’s talk about the adjacency matrix. Given some graph with vertices , we can build a matrix where the ‘th row has a at the ‘th column if and only if is connected to via an edge. Let be a if an edge exists between and , and a otherwise; note, will always be due to our prior assumption that no vertex is connected to itself. It’s also worth noting that . Our adjacency matrix will look something like this
It’s also worth noting that because , so our matrix will be symmetric.
There’s also a variant of the adjacency matrix called the Laplacian matrix. It is easily constructed from the adjacency matrix; simply take the adjacency matrix, negate it, and for every entry on the diagonal, set its value to the degree of .
Notice that because of this, the sum of every row and column of the Laplacian is 0 – this is because the diagonal entry denotes the degree of the vertex, and the other entries in the column not on the diagonal represent each edge connecting to the vertex. This is the definition of the degree, so they cancel out.
I am not a graph theory expert by any means, and my linear algebra skills have faded away, but I figured that one could use some properties of the Laplacian and bipartite graphs to elegantly generate some solution. However, after some light probing, I found no succint solution. If any of you reading this are graph theory experts and find some nice answer from this, hmu.
For those of you that read my last post, you probably have an intuition of what’s coming next. If you’re fuzzy on how to count with polynomial coefficients, you should check out my last post for a brief overview.
Hopefully you have an idea of where this is going now. We can represent classes as variables, , where is the number of classes. Let’s also define as the number of students in class . Now, for students , where is the number of students, let’s define as the set of classes that student is in.
Now, our answer is simply the coefficient of in the following expression
Personally, I often find combinations of fancy mathematical symbols very hard to understand, even though they’re so fun to write. Let’s break this down below.
Imagine our humble liberal arts college has students, and classes, . We still pay $70,000 a year in tuition.
Class has students
Class has students
Class has students
Now suppose Thanos comes to a poetry recital and joins the audience in snapping after student finishes their poem. How many ways are there to halve the size of each class, while also halving the size of the entire school?
Let’s enumerate how each student contributes to our multinomial.
Remember that a student is either in all of their classes, in the case they don’t get removed, or in none of their classes, in the unlucky chance that they do. That’s why we only have two terms.
Now the solution to our problem is simply the coefficient of in the following expression
If you haven’t noticed yet, there is still technically something wrong with this solution. Removing half of the students from each class does not guarantee that half of the students from the entire populus are removed. For instance, if we get rid of students , we successfully halve the size of each class, but we only removed of the total population! Thanos would be ashamed.
Luckily, there is an easy fix. Let’s just define some fake class that every student is in, and add a constraint halving this fake class as well. Now we’ve done it! If we call our fake classroom , our final expression would look like this
The coefficient we’re now looking for is
This is a super tedious calculation to carry out by hand. Because of this, I made a little coefficient calculator. If you want to see it in action, I made a gist instantiating the calculator with the problem described above. Apparently, there are ways to remove students such that each class (and technically ) has half of the original students.
Tada, we did it! I’m sure Thanos is marveling at this blog post (haha get it), and I hope you learned something from it too!
I figured I’d brainstorm some variants to this problem that might be interesting to think about
- Given a student on campus, what is the probability of them getting removed when Thanos snaps his fingers?
- If every student gets removed from the campus with a uniform likelihood , what’s the probability that the remaining distribution of students on campus would please Thanos?
If you come up with any neat solutions to these problems, feel free to email me to talk about it!
Thanks for reading!