Ponder This Challenge - July 2026 - Return of the Superheroes

Return of the Superheroes

Continuing the theme of last month, we deal with a movie franchise consisting of $n$ superheroes. They are joined by $n$ supervillains. The producers intend to pair the superheroes and the supervillains to form (hero, villain) pairs where each hero has a unique villain serving as their nemesis.

Each pairing is accepted differently by the audiences. After elaborate work, a method of assigning numerical value $f(a,b)$ to each pairing $(a,b)$ to estimate the audiences' reaction was developed. The producers wish to find the list of pairings that maximizes the value of the pairing with the minimal value in the list. This minimal value is called the hero-villain value.

The way $f(a,b)$ is computed is as follows: Let $p$ be some prime and define a function $T_{a,b}(x)=x^2+ax+b\ (\text{mod}\ p)$. By setting $x_0=0$ and $x_{n+1}=T(x_n)$ we obtain a sequence $x_0,x_1,x_2,\ldots$ which eventually repeats. Let $f(a,b)$ be the number of steps until the first repeat happens. i.e. if $x_n$ is the first element in the sequence such that there exists $m<n$ for which $x_n=x_m$, then $f(a,b)=n$.

For example, for $n=5$ and $p=101$, one possible list of pairings is $(1,3), (2,1), (3,4), (4,2), (5,5)$ which yields the values $14, 18, 19, 22, 14$ for which the minimum is 14. It turns out that every list of pairings gives a value of at most 14, so 14 is hero-villain value for this case.

Your goal Find the hero-villain value for $n=611$ and $p=14411$

A bonus "*" will be given for finding the optimal $n$ in the range $1<n<N$ for $N=1000$ which gives the maximal hero-villain value for $n$ and $p=17377$.

Solution

• Click here to view the solution

  The numerical solutions are 349 for the main riddle, and $n=924$ for the bonus (giving the hero-villain value 408). Every $n$ giving the value 408 was accepted; by "optimal" we only meant "giving the maximum hero-villain value for $n$ in this range".

  Each pairing is a permutation, and so the riddle can be rephrased in the following manner: Given some $n\times n$ matrix, pick $n$ values not sharing row or column, such that the smallest value among them is as large as possible. This is one variant of a bottleneck assignment problem. Similar to the previous superhero problem, the key for solving this is graph matching.

  To actually find the hero-villain value we use binary search. For a given $k$, we attempt to determine whether there is some permutation giving at least $k$ by constructing a bipartite graph where a hero is matched with a villain only if their value is at least $k$. All that remains is finding a perfrect matching in this graph, which can be solved using the Hopcroft-Karp algorithm which was useful in the previous superhero riddle as well.

Solvers

• *Alper Halbutogullari (6/7/2026 6:45 AM IDT)
• *Stéphane Higueret (6/7/2026 4:10 PM IDT)
• Ashfaque Shaikh (6/7/2026 4:21 PM IDT)
• *Tamir Ganor & Shouky Dan (6/7/2026 4:24 PM IDT)
• *Juergen Koehl (6/7/2026 4:32 PM IDT)
• Alex Fleischer (6/7/2026 4:42 PM IDT)
• *Daniel Bitin (6/7/2026 4:45 PM IDT)
• *Nadir S. (6/7/2026 5:00 PM IDT)
• *Rob Pratt (6/7/2026 5:09 PM IDT)
• *Paul Lupascu (6/7/2026 5:26 PM IDT)
• Ruben Menendez (6/7/2026 5:44 PM IDT)
• *Daniel Chong Jyh Tar (6/7/2026 5:57 PM IDT)
• *Lazar Ilic (6/7/2026 5:58 PM IDT)
• Ahmet Yüksel (6/7/2026 6:23 PM IDT)
• *Bertram Felgenhauer (6/7/2026 6:42 PM IDT)
• *Jean-François Hermant (6/7/2026 7:52 PM IDT)
• *Micah Day-O'Connell (6/7/2026 8:37 PM IDT)
• *Lyes Belhoul (6/7/2026 8:44 PM IDT)
• *Evert van Dijken (6/7/2026 9:46 PM IDT)
• *Nickita Khylkouski (6/7/2026 9:54 PM IDT)
• *Jason Shaw (6/7/2026 9:59 PM IDT)
• *King Pig (6/7/2026 11:19 PM IDT)
• *Franciraldo Cavalcante (7/7/2026 12:37 AM IDT)
• *Prashant Wankhede (7/7/2026 1:02 AM IDT)
• Shirish Chinchalkar (7/7/2026 2:15 AM IDT)
• *Limen (7/7/2026 4:05 AM IDT)
• *Kang Jin Cho (7/7/2026 4:24 AM IDT)
• *Guangxi Liu (7/7/2026 4:41 AM IDT)
• *Vamsi Krishna Talupula (7/7/2026 8:44 AM IDT)
• *Tomodovodoo (7/7/2026 12:58 PM IDT)
• *Mark Buisseret (7/7/2026 1:16 PM IDT)
• *Dan Dima (7/7/2026 3:22 PM IDT)
• *Daksh Bhatnagar (7/7/2026 4:05 PM IDT)
• *Carter Tran (8/7/2026 12:43 AM IDT)
• *Jackson La Vallee (8/7/2026 4:16 AM IDT)
• *Harold Gutch (8/7/2026 8:09 AM IDT)
• *Abraham Joshua (8/7/2026 1:39 PM IDT)
• *Michael Vahle (8/7/2026 1:58 PM IDT)
• *Lucas Reymond (8/7/2026 2:17 PM IDT)
• *Paul Shaw (8/7/2026 2:58 PM IDT)
• *Jiao Baocheng (8/7/2026 3:40 PM IDT)
• Resnina Tathyana (8/7/2026 11:53 PM IDT)
• *Dominik Reichl (9/7/2026 11:21 AM IDT)
• *Vladimir Volevich (9/7/2026 12:16 PM IDT)
• *Nicolas Lopez (9/7/2026 5:47 PM IDT)
• *Asaf Zimmerman (10/7/2026 12:28 AM IDT)
• Gary M. Gerken (10/7/2026 5:55 AM IDT)
• *Peter Ji (10/7/2026 12:06 PM IDT)
• *Abhishek Sekar (10/7/2026 6:44 PM IDT)
• *Parth Rana (10/7/2026 7:16 PM IDT)
• *Kevin Funchal (11/7/2026 5:14 AM IDT)
• *Rethna Pulikkoonattu (11/7/2026 11:45 PM IDT)
• *David F.H. Dunkley (11/7/2026 11:52 PM IDT)
• *Hakan Summakoğlu (12/7/2026 1:05 AM IDT)
• *Steffen Wolf (12/7/2026 3:01 PM IDT)
• *Hugo Pfoertner (12/7/2026 8:45 PM IDT)
• Karl D’Souza (13/7/2026 1:33 AM IDT)
• *George Weale (13/7/2026 8:48 AM IDT)
• *Maksim Silchenko (13/7/2026 11:11 AM IDT)
• *Sanandan Swaminathan (13/7/2026 12:39 PM IDT)
• Bobby Proffitt (13/7/2026 4:22 PM IDT)
• José Eduardo Gaboardi de Carvalho (13/7/2026 4:45 PM IDT)
• *Shyamalan Kannan (13/7/2026 10:37 PM IDT)
• *Charvik Reddy Mukku (13/7/2026 10:58 PM IDT)
• *Serge Thill (14/7/2026 2:17 PM IDT)
• *Hagen von Eitzen (14/7/2026 10:51 PM IDT)
• *Jatin Garg (15/7/2026 9:45 PM IDT)
• Radu-Alexandru Todor (16/7/2026 1:36 AM IDT)
• Simon Atileh (17/7/2026 12:11 AM IDT)
• *Zidane Virani (17/7/2026 6:49 AM IDT)
• *John Tromp (18/7/2026 1:58 PM IDT)
• *Nyles Heise (19/7/2026 7:28 AM IDT)
• Rajesh Sathiyanarayanan (19/7/2026 12:07 PM IDT)
• *Bert Dobbelaere (19/7/2026 8:49 PM IDT)
• *Liubing Yu (20/7/2026 2:45 AM IDT)
• *Patricia Ji (20/7/2026 6:35 AM IDT)
• *George Jiri Spitalsky (20/7/2026 9:53 AM IDT)
• *Mark Zhu (21/7/2026 2:38 AM IDT)
• Iván Rendo Barreiro (21/7/2026 12:59 PM IDT)
• *Vassili Chesterkine (23/7/2026 11:38 AM IDT)
• *Henk Waßmann (24/7/2026 2:09 AM IDT)
• *Siamak Alimirzazadeh (25/7/2026 11:54 AM IDT)
• *Bao Nguyen (26/7/2026 10:15 AM IDT)
• *Lorenz Reichel (27/7/2026 9:32 AM IDT)
• *Latchezar Christov (27/7/2026 3:19 PM IDT)
• *Fakih Karademir (28/7/2026 12:24 AM IDT)
• *Khaled Alam (28/7/2026 5:47 AM IDT)
• *Raviteja Rao Jupally (28/7/2026 1:59 PM IDT)
• *Jack Saleeby (28/7/2026 11:45 PM IDT)
• *Jan Fricke (29/7/2026 7:23 AM IDT)
• *Govind Raj Jujare & Hansraj Nahata (29/7/2026 7:03 PM IDT)
• *Sandipan Dey (29/7/2026 11:24 PM IDT)
• *Motty Porat (30/7/2026 2:27 AM IDT)
• Sathi Gnaneswara Reddy (30/7/2026 7:29 AM IDT)
• Valmik Nahata (30/7/2026 12:44 PM IDT)
• *Armin Krauß (30/7/2026 11:58 PM IDT)
• Fabio Michele Negroni (31/7/2026 4:11 PM IDT)
• *Justin Mazenauer (31/7/2026 4:47 PM IDT)
• *Reiner Martin (31/7/2026 7:00 PM IDT)
• *Achyuth Jayadevan (31/7/2026 9:29 PM IDT)
• *David Smalling (1/8/2026 7:11 AM IDT)
• *David Greer (2/8/2026 10:34 PM IDT)
• Michael Schuresko (3/8/2026 4:17 AM IDT)
• *Tongyang Song (3/8/2026 3:18 PM IDT)
• *Alexander Bielik (4/8/2026 1:32 AM IDT)
• Marco Bellocchi (5/8/2026 2:37 AM IDT)
• *Li Li (5/8/2026 9:03 AM IDT)
• Kai Guttmann (7/8/2026 10:11 AM IDT)