Heroes, villains, and one prime
You are handed n heroes, numbered a = 1 up to n, and n villains, numbered b = 1 up to n. A single prime p sets the arena. Your job is to pair every hero with exactly one villain.
Each possible pairing of a hero a with a villain b has a strength, and it comes from a little dynamical system. Start at zero and repeatedly apply the map T(x) = x² + a·x + b (mod p), so x₀ = 0, then x₁ = T(x₀), then x₂ = T(x₁), and so on. Because there are only p possible values, the sequence must eventually revisit somewhere it has already been. The score f(a,b) is how many steps it takes before that first repeat, which is one way of measuring how long the hero survives the villain's map before it falls into a loop.
Now pair everyone up, one hero to one villain, a clean one-to-one matching. Every matching has a whole set of scores, one per pair, but you are graded on a single number: the smallest score in your matching, its weakest pairing. The hero-villain value is the largest weakest-link you can reach, taken over every possible way of pairing them. Push the floor as high as it will go, and report the point where it stops.
Return of the Superheroes
p = 14411
find the hero-villain value
How high can it go
n ranges over 1 < n < 1000
find the maximum value, and where
The puzzle ships a small case to check your understanding: with n = 5 and p = 101, the hero-villain value is 14. My solver lands on 14 for that case before it is allowed to touch anything larger, which is the first sign the scoring and the matching are both wired up correctly.
The orbit behind each score
Before any matching, you need the score for every single hero-villain pair, and that score is a walk. Fix a hero a and a villain b and set the map loose from zero. Each step lands on a new residue mod p, and for a while the walk keeps finding fresh ground, a straight-ish tail of never-seen values. Then it steps onto somewhere it has already stood, and from that point on it is trapped forever in a cycle. The picture this traces is the shape mathematicians call a rho: a tail leading into a loop, like the Greek letter ρ.
The score f(a,b) is the total number of distinct places the walk visits before it repeats, the tail length μ plus the cycle length λ. A hero who wanders a long way before getting caught scores high; one who falls into a short loop almost immediately scores low. Drag the two sliders below to choose a hero and a villain, and watch the walk build its rho in real time, at the small prime p = 101 so the whole thing fits on screen.
Do this for all n heroes against all n villains and you get an n × n table of scores, one row per hero, one column per villain. That table is the entire input to the matching problem. For the main challenge it is a 611 × 611 grid of walk-lengths; every answer on this page is a statement about how you are allowed to pick one entry from each row and each column of that grid.
Raising the floor as high as it will go
The problem has a simple shape. You have that grid of scores, you choose a one-to-one matching, one villain per hero with no villain used twice, and you are judged only by the smallest score you picked. The task is to make that minimum as large as possible. This is a classic setup with a classic name, the bottleneck assignment problem, and there is a neat way to solve it.
Instead of hunting for the best matching directly, pick a target floor t and ask a yes-or-no question: can I pair everyone using only pairings that score at least t? Throw away every grid entry below t, and see whether a perfect one-to-one matching still survives in what is left. If it does, the floor t is reachable; if it does not, t is set too high. This question only gets harder as t rises, since a low floor leaves the grid dense and easy to match, while a high floor leaves it sparse and eventually impossible. So the answer is the highest t that still lets everyone pair up, and you can find it by binary search.
Drag the threshold below on a small p = 101 board. Every cell is a hero-villain score; raise t and the cells that fall below it dim out. A matching engine re-solves live on what remains, lighting the pairs it chooses. As you push t up the matching thins out and eventually fails. The last floor that still holds is the hero-villain value for this small board.
The main challenge, and its certificate
Run that procedure on the real grid, with 611 heroes, 611 villains and p = 14411, and the floor rises to a point where it can go no higher.
That last sentence is really the whole proof, and it comes in two halves. One is a witness: an actual list of 611 pairs, each villain used once, whose weakest pairing scores exactly 349, which I submitted as a file. The other is a wall: once the floor is pushed to 350 no perfect matching survives, so nothing higher than 349 is possible. With a witness sitting at the value and no matching just above it, the number is fixed on both sides.
One quiet detail makes the value trustworthy rather than lucky. The matching is free to make most pairs much stronger than the floor, and only a handful are forced down to 349. The histogram below is the real distribution of the 611 scores in my submitted matching: a firm edge on the left at 349, most of the weight in the 350s and 360s, and a thin tail of pairings that reach past 500. The bottleneck is set by that left edge alone, and everything to its right is spare strength the matching kept because it did not need to give it up.
How high it can go, and where it stops
The bonus changes the prime to p = 17377 and lets n roam across the whole range 1 < n < 1000. Every n gives its own board and its own hero-villain value. The question is where that value peaks. So I computed it for all of them, 998 boards and 998 values, and drew the curve.
The climb is not smooth. For small n the value is jittery, because a board with only a handful of heroes can be unlucky and get dragged down by one forced weak pairing, or be lucky and sit high. As n grows the matching has more room to work with, and the value settles into a steady rise: past 300 around n = 58, past 350 near n = 193, past 400 at n = 671. Near the top of the range it flattens out.
So the bonus answer is 408, and the fuller story is that it is reached by every n in the contiguous stretch [924, 999], first arriving at 924 and not dropping again within the allowed range.
Computed two independent ways
Two numbers, 349 and 408, are easy to state and easy to get subtly wrong, so nothing on this page rests on a single code path. Every load-bearing quantity is computed two independent ways, and the answer is only reported where they agree.
The submission went to IBM Research on 13 July 2026, with the full 611-pair matching attached, and was confirmed correct. The rest is just the pleasure of a problem that turned a question about looping sequences into a question about the strongest way to pair off a room full of heroes and villains.