The Thanos Problem

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 $n$ other vertices, it has a degree of $n$. 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 $v_1 \dots v_n$, we can build a matrix where the $i$‘th row has a $1$ at the $j$‘th column if and only if $v_i$ is connected to $v_j$ via an edge. Let $e_{i,j}$ be a $1$ if an edge exists between $v_i$ and $v_j$, and a $0$ otherwise; note, $e_{i,i}$ will always be $0$ due to our prior assumption that no vertex is connected to itself. It’s also worth noting that $e_{i,j} = e_{j,i}$. Our adjacency matrix will look something like this

$$\begin{bmatrix} 0 & e_{1,2} & e_{1,3} & \dots & e_{1,n} \\ e_{2,1} & 0 & e_{2,3} & \dots & e_{2,n} \\ e_{3,1} & e_{3,2} & 0 & \dots & e_{3,n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ e_{d,1} & e_{d,2} & e_{d,3} & \dots & 0 \end{bmatrix}$$

It’s also worth noting that because $e_{i,j} = e_{j,i}$, 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 $L_{i, i}$ on the diagonal, set its value to the degree of $v_i$.

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.

Multinomial Coefficients!

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, $c_1 ... c_m$, where $m$ is the number of classes. Let’s also define $\vert c_i \vert$ as the number of students in class $c_i$. Now, for students $s_1 ... s_k$, where $k$ is the number of students, let’s define $\zeta_i$ as the set of classes that student $s_i$ is in.

Now, our answer is simply the coefficient of $\displaystyle \prod_{i=1}^{m} {c_{i}^{\vert c_{i} \vert / 2}}$ in the following expression

$$\displaystyle \prod_{i=1}^{k} {(1 + \prod_{c_j \in \zeta_i}^{} {c_j})}$$

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.

Example College

Imagine our humble liberal arts college has $8$ students, $a, b, c, d, e, f, g, h$ and $3$ classes, $x, y, z$. We still pay $70,000 a year in tuition.

Class $x$ has students $a, b, c, d$

Class $y$ has students $c, d, e, f$

Class $z$ has students $a, c, g, h$

Now suppose Thanos comes to a poetry recital and joins the audience in snapping after student $a$ 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.

Student $a$ is $(1 + xz)$

Student $b$ is $(1 + x)$

Student $c$ is $(1 + xyz)$

Student $d$ is $(1 + xy)$

Student $e$ is $(1 + y)$

Student $f$ is $(1 + y)$

Student $g$ is $(1 + z)$

Student $g$ is $(1 + z)$

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 $x^2 y^2 z^2$ in the following expression

$$(1 + xz)(1 + x)(1 + xyz)(1 + xy)(1 + y)(1 + y)(1 + z)(1 + z)$$

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 $a, c, d$, we successfully halve the size of each class, but we only removed $3/8$ 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 $w$, our final expression would look like this

$$(1 + xzw)(1 + xw)(1 + xyzw)(1 + xyw)(1 + yw)(1 + yw)(1 + zw)(1 + zw)$$

The coefficient we’re now looking for is $x^2 y^2 z^2 w^4$

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 $8$ ways to remove $4$ students such that each class $x, y, z$ (and technically $w$) 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!

Potential Variants

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 $p_r$, 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!