Return of the superheroes — Achyuth Jayadevan

There are $611!$ ways to pair 611 heroes with 611 villains. The proof of the optimal score fits around one of them: villain 493.

Even its strongest possible opponent reaches only 349. Every complete assignment must use that villain, so 349 is a ceiling. The other half of the solution is to find an assignment that reaches the ceiling without any weaker pair. A huge optimization problem becomes two pieces of evidence: one arrangement, one unavoidable limit.

The interesting part is how to discover those pieces without trying every arrangement.

When a sequence meets itself

There are $n$ superheroes and $n$ villains. Each hero must face exactly one villain, and every villain must be used. The strength of a pair is determined by a modular dynamical system. The strength of the entire assignment is the strength of its weakest pair.

The July 2026 IBM Ponder This puzzle asks for the best possible assignment. For hero $a$ and villain $b$ , start at zero and iterate

$x_0=0,\qquad x_{j+1}=x_j^2+ax_j+b\pmod p.$

Let $f(a,b)$ be the index of the first repeated state. Equivalently, it is the number of distinct states visited before the first collision. Since there are only $p$ residues, a repeat must occur.

For a permutation $\pi$ assigning villains to heroes, the bottleneck is $\min_a f(a,\pi(a))$ . The optimization problem is

$B(n,p)=\max_{\pi\in S_n}\;\min_{1\le a\le n}f(a,\pi(a)).$

This is not a maximum-total-score problem. A spectacular pair cannot compensate for one weak pair. That is why greedy choices by individual heroes can get in each other’s way.

My two-page solution organizes the argument around two certificates: an assignment that reaches the claimed value, and an obstruction that prevents a higher one. This article expands the reduction and supplies independently generated matching data.

Hear a collision happen

Every function on a finite set has the same basic orbit shape: a nonrepeating tail followed by a cycle. Write $\mu$ for the tail length and $\lambda$ for the cycle length. The first collision happens at time $\mu+\lambda$ .

In the five-hero example with $p=101$ , hero 1 facing villain 3 gives

$0,3,15,41,8,75,47,37,96,23,50,28,7,59,\underline{8},\ldots$

There are four tail states and ten cycle states. The repeated 8 closes the loop, so $f(1,3)=14$ . The number we care about is not the residue 8; it is the collision time 14.

The trailing thread joins a closed cycle. Beads mark the actual orbit states modulo 101; the woven thickness and pitch are illustrative.

A trailing bundle joins the woven loop. Playback follows the beads through the tail and around the cycle; the highlighted thread closes when the orbit repeats. The three-dimensional shape is a drawing of this structure, not an additional invariant. Sound follows the residues through an eight-note pentatonic range. Two residues can share a pitch, so a musical repetition is not, by itself, evidence of a repeated mathematical state; the diagram and counters track the actual residues.

Evaluating every pair separately repeats a lot of computation. The quadratic has two parameters, but a translation puts it into a one-parameter family.

Because $p$ is an odd prime, two is invertible in $\mathbb F_p$ . Define

$s=\frac a2,\qquad c=b+s-s^2,\qquad y=x+s.$

All of these operations are in the finite field. The fraction $a/2$ means multiplication by the modular inverse of two, not ordinary floating-point division. Then

$T_{a,b}(x)+s=(x+s)^2+c,$

so the translated recurrence becomes

$q_c(y)=y^2+c,\qquad y_0=s.$

Translation is a bijection. It preserves equality and the first collision time, yielding

$f(a,b)=\mu_c(s)+\lambda_c(s).$

The starting state changes to $s$ ; replacing the recurrence while leaving its start at zero would give the wrong problem.

The benefit is shared structure. Pairs with the same $c$ traverse the same functional graph of $q_c$ , possibly from different starting states. Group those pairs, and memoize the tail and cycle data for discovered states. A new walk either reaches an already solved state or finds a cycle within its current path. In the first case, propagate known distances backward. In the second, assign the new cycle length, then walk backward through its tail.

With per- $c$ memoization, each discovered $(c,y)$ state is solved once. This is an opportunity to avoid repeated walks; it is not a claim that every input visits only a small number of states. A dense table for all $p^2$ possibilities can be large, so sparse storage or processing one $c$ at a time is useful.

Turn a score into a yes-or-no question

Fix a threshold $t$ . Draw a bipartite graph with heroes on the left and villains on the right. Keep exactly the pairs strong enough to survive:

$(a,b)\in E(G_t)\quad\Longleftrightarrow\quad f(a,b)\ge t.$

A perfect matching picks $n$ edges with no shared endpoint. Such a matching exists exactly when every hero can be assigned a different villain while keeping all scores at least $t$ . Therefore

$B(n,p)=\max\{t:G_t\text{ has a perfect matching}\}.$

Raising the threshold only deletes edges. Feasibility is monotone, so we can binary-search it. For each threshold, an augmenting-path algorithm finds a maximum matching. Hopcroft–Karp improves the search by processing shortest augmenting paths in batches, with a standard bound of $O((m+n)\sqrt n)$ for a graph with $m$ edges and $O(n)$ vertices.

Scores

Five anchors on each side. Fine threads are eligible pairs; woven bundles are the matching. Raise the threshold to remove weak connections. Hover over a thread to hear its score.

At threshold 14, a perfect matching exists. At 15, it does not. One optimal assignment in IBM’s example is

$\pi=(3,1,4,2,5),\qquad (f(a,\pi(a)))_{a=1}^5=(14,18,19,22,14).$

The sculpture may highlight a different optimal assignment; the bottleneck, rather than a particular permutation, is the invariant being optimized.

An augmenting path alternates between unused and chosen edges. Flipping their status assigns one more hero without unassigning anyone overall. This is why an early locally convenient choice need not be permanent.

Two certificates meet in the middle

A perfect matching at threshold $t$ proves $B(n,p)\ge t$ . That is the lower certificate. To prove equality we also need $B(n,p)<t+1$ .

Hall’s theorem supplies the general upper certificate: a set of heroes $S$ whose available villain neighbors $N(S)$ satisfy $|N(S)|<|S|$ . Too many heroes are competing for too few villains. The same statement works after exchanging the two sides.

An isolated vertex is the smallest possible obstruction. If one villain has no incident edge at threshold $t+1$ , every assignment necessarily fails that threshold. More generally, the strongest possible partner of every vertex gives the bound

$B(n,p)\le\min\left\{\min_a\max_b f(a,b),\;\min_b\max_a f(a,b)\right\}.$

This bound need not always be sharp. Every vertex can have a surviving edge while a larger Hall-deficient set still prevents a perfect matching. For the large instances here, however, single-vertex obstructions are enough. That makes the final proof much smaller than the search that discovered it.

Why the required answer is 349

Villain 493 is the bottleneck. An exact scan of its possible opponents gives

$\max_{1\le a\le611}f(a,493)=f(402,493)=349,$

with hero 402 the unique maximizer. Every complete assignment must use villain 493, so no assignment can have bottleneck above 349.

For the other direction, a permutation assigns hero 402 to villain 493 with score 349 and gives every other hero a pair scoring at least 350. This is slightly stronger than merely finding a perfect matching at 349. It isolates the single edge that determines the optimum.

The downloadable certificate contains such a permutation. Its villain indices are one-based, in hero order. Verification needs only three things: the correct length, no duplicate villains, and the orbit score of every chosen pair. Together with the column maximum, this proves

$\boxed{B(611,14411)=349.}$

The upper bound is as important as the assignment. A large list of strong pairs, on its own, shows success at one threshold but says nothing about whether a better assignment exists.

The bonus: a threshold at 924

Now hold $p=17377$ fixed and vary the number of heroes and villains together. Four exact maxima explain the entire range:

Vertex	Partners included	Largest score
Villain 1	Heroes 1–490	404
Hero 145	Villains 1–777	405
Hero 759	Villains 1–999	408
Villain 513	Heroes 1–923	405

At threshold 409, the first three rows cover every possible size. Villain 1 is isolated for $2\le n\le490$ ; hero 145 is isolated for $491\le n\le777$ ; hero 759 is isolated for $778\le n\le999$ . Thus no permitted size can achieve 409.

At threshold 408, villain 1 and hero 145 again rule out the first two ranges. Villain 513 rules out $778\le n\le923$ . Therefore no size below 924 can reach 408.

A perfect matching for $n=924$ supplies the missing lower bound. This proves both the bonus optimum and the smallest size achieving it.

The solution goes a step further. Introduce hero 925 and villain 925, then repair the existing matching with an augmenting path at threshold 408. Repeat through size 999. The generated certificate records only the assignments changed at each extension, rather than storing 75 nearly identical full permutations.

These extensions deserve checking: adding a hero and a villain does not automatically preserve the existence of a perfect matching at a fixed threshold. Here the explicit alternating-path updates provide that proof. Combined with the obstruction at 409, they give

$\operatorname*{arg\,max}_{2\le n\le999}B(n,17377)=\{924,925,\ldots,999\}.$

Check the evidence

The attached write-up states the existence of the matching certificates but does not print the permutations. For this article, a separate implementation recomputed the orbit scores directly, found the required matchings, and checked all four bonus maxima. It deliberately uses direct orbit traversal rather than the shared-state reduction above, so the numerical cross-check does not depend on the memoization implementation.

The core orbit calculation is short:

def first_repeat(a, b, p):
    seen = set()
    x = 0
    while x not in seen:
        seen.add(x)
        x = (x*x + a*x + b) % p
    return len(seen)


def verifies_pairing(permutation, p, threshold):
    n = len(permutation)
    if sorted(permutation) != list(range(1, n + 1)):
        return False
    return all(
        first_repeat(a, b, p) >= threshold
        for a, b in enumerate(permutation, start=1)
    )

This is an executable numerical checker, not a Lean formalization. The article’s accompanying C++ program generates the main permutation, the bonus base permutation, and every extension; it asserts the bounds before writing the certificate file. The website tests independently recheck the emitted matchings and obstruction scores.

To reproduce the certificate file with a C++17 compiler:

c++ -O3 -std=c++17 verify-superheroes.cpp -o verify-superheroes
./verify-superheroes > superheroes-certificates.json

This separates the roles cleanly. Search discovers a candidate. A permutation certifies feasibility. A row or column maximum certifies the obstruction. The final answer rests on the two certificates meeting at the same integer.

Context and sources

IBM’s July 2026 challenge and published solution give the puzzle, the five-hero example, the required answer 349, and a bonus answer of $n=924$ with value 408. The solver list credits Achyuth Jayadevan with a bonus solution. IBM notes that other optimal sizes were also accepted; the argument here identifies the smallest and the entire optimal interval.

The threshold-graph method is an instance of bottleneck matching. The classical algorithmic reference is Hopcroft and Karp’s An $n^{5/2}$ Algorithm for Maximum Matchings in Bipartite Graphs, published in 1973. The interactive sculpture and the independent certificate generator use a simpler augmenting-path implementation; their purpose is transparency at these fixed instance sizes.

The distinctive feature of this solution is how little of the computed graph is needed for the final upper bound. Hundreds of thousands of orbit scores collapse into a handful of maxima. A global optimization problem ends with one unavoidable opponent.