Optimal Covering of Superhero Team Combinations using Boolean Lattices and Matching Algorithms.
This project was developed for IBM Research’s June 2026 Ponder This challenge, “The Superhero Team Movies.” The problem can be stated as a combinatorial optimization task: given n superheroes, construct a sequence of movies that covers every non-empty subset of heroes while minimizing the total number of action scenes. Each movie follows a strict nested structure: it starts with one hero, then adds one new hero at a time, so every movie corresponds to a saturated chain in the Boolean lattice of all hero subsets.
I modeled the problem using order theory and interpreted each possible team as a node in the Boolean lattice Bₙ. The key difficulty is that every subset must be covered, but repeated scenes should be minimized. I first derived a lower bound on the number of required scenes by counting how many chains must reach each rank of the lattice. This gave a natural optimality target based on the maximum binomial coefficient above each rank.
To reach this bound constructively, I implemented an algorithm based on symmetric chain decompositions. The upper half of the Boolean lattice is covered using a recursive symmetric chain decomposition, while the lower ranks are completed through a sequence of bipartite matching problems. This ensures that every subset is covered and that the number of scenes at each rank matches the theoretical lower bound.
The final Python implementation generates compact solutions in the notation required by the challenge, verifies that all non-empty subsets are covered, and checks that the achieved number of scenes is equal to the theoretical optimum. For n = 6, the algorithm finds an optimal franchise with 82 scenes across 20 movies. The same approach also scales to the bonus case n = 10, producing an optimal construction with 1,646 scenes across 252 movies.
This project combines discrete mathematics, combinatorial optimization, algorithm design, and rigorous verification. It was a good opportunity to turn a playful puzzle into a formal mathematical model, prove optimality, and implement a reproducible solution in Python.