Ponder This Challenge - March 2026 - Path game on a hole-riddled chessboard

Given an $N\times M$ board and a starting location $(x,y)$ with $1\le x\le N$ and $1\le y\le M$, Alice and Bob play the following game: Alice begins by placing a pawn on square $(x,y)$, then Bob moves the pawn to an adjacent square of the four potential neighboring squares (diagonals don't count) and removes the square the pawn left from the board. Alice makes the next move, and they alternate until a player has no possible move and loses the game.

Since this is a game obeying Zermalo's theorem, given $N\times M$ and $(x,y)$ either Alice can force a win, or Bob can force a win. Call $(x,y)$ an "A" square for the board if Alice can force a win, and "B" if Bob can force a win.

To complicate the game, we can remove some of the squares in the board before the game begins, in the following manner. Fix two prime numbers $p,q$, and label each square in the board with a number, such that square $(i,j)$ is labelled $p^i+q^j$ (recall that indexing starts from 1, not 0). Now, pick a prime number $s$, and remove from the board all the squares whose label is divisible by $s$.

For example, it can be seen that for $N=M=3$, the board is

But if we choose $p=19, q=2, s=5$, as $19^2+2^2=365$ which is divisible by 5 the board becomes

With # denoting the missign square in the middle.

Given a board size $N\times M$, two primes $p,q$ and a set $S$ of prime numbers, for each $s\in S$ we can count the number of "A" and "B" squares in the board (we don't count "#"). We can then sum those values over all the possible $s\in S$.

For example, for $N=M=3$ and $p=19, q=2$ and $S = [2,3,5,7,11]$ we have a total of $16$ "A" and $19$ "B".

Your goal: Find the total number of "A" and "B" for $N=M=157$, $p=419, q=211$ and $S$ being the set of all prime numbers lower than 100.

A bonus "*" will be given for finding the total number of "A" and "B" for $N=M=1557$, $p=419, q=211$ and $S$ being the set of all prime numbers lower than 500.

Solution

• Click here to view the solution

  The numerical solutions are:

  • For $n=157$:
    • Total A: 259501
    • Total B: 280200
  • For $n=1557$:
    • Total A: 109008067
    • Total B: 112989820

  Iterating over all cases is simple. The challange in the riddle is - given a specific board, how to find the "A" and "B" squares in it.

  This is an example of the undirected vertex geometry game, which can be played in general on any finite undirected graph, and there is a relatively simple graph-theoretic criterion: A vertex is an "A" vertex (whoever starts on it can force a win) if there exists a maximum matching of the graph that does not contain that vertex.

  Since the graph in question is bipartite, one can use the Hopcroft-Karp algorithm to find one maximum matching. Once such a matching is found, the Dulmage–Mendelsohn decomposition can be used to identify which vertices are part of every maximum matching of the graph.

Solvers

• *Lazar Ilic (1/3/2026 12:48 AM IDT)
• *Alper Halbutogullari (1/3/2026 3:55 AM IDT)
• *Prashant Wankhede (1/3/2026 4:54 AM IDT)
• *Paul Lupascu (1/3/2026 9:09 AM IDT)
• Ahmet Yuksel (1/3/2026 12:21 PM IDT)
• Abraham AJ Arshad (1/3/2026 2:18 PM IDT)
• *Jean-françois Hermant (1/3/2026 6:01 PM IDT)
• *Juergen Koehl (1/3/2026 11:06 PM IDT)
• *Bertram Felgenhauer (2/3/2026 1:53 AM IDT)
• *Rahid Zaman (2/3/2026 6:18 AM IDT)
• *Guangxi Liu (2/3/2026 8:04 AM IDT)
• *Pitiwat Chimplee (2/3/2026 8:16 AM IDT)
• Stephen Ebert (2/3/2026 10:13 AM IDT)
• *Daniel Chong Jyh Tar (2/3/2026 11:47 AM IDT)
• Alex Fleischer (2/3/2026 5:27 PM IDT)
• *Jack Saleeby (2/3/2026 7:37 PM IDT)
• Stéphane Higueret (2/3/2026 9:40 PM IDT)
• *Jan Ondras (3/3/2026 2:59 AM IDT)
• *Franciraldo Cavalcante (3/3/2026 4:17 PM IDT)
• Anshul Agarwal (4/3/2026 1:14 PM IDT)
• *Michael Vahle (4/3/2026 2:36 PM IDT)
• *Kang Jin Cho (4/3/2026 7:40 PM IDT)
• *King Pig (5/3/2026 4:11 AM IDT)
• *Rethna Pulikkoonattu (5/3/2026 9:14 PM IDT)
• Gürkan Koray Akpınar (6/3/2026 11:31 AM IDT)
• *Peter Moser (6/3/2026 5:17 PM IDT)
• *George Jiri Spitalsky (7/3/2026 10:47 AM IDT)
• *Shouky Dan & Tamir Ganor (7/3/2026 8:32 PM IDT)
• *Reda Kebbaj (8/3/2026 11:40 AM IDT)
• *Chern Arthas (9/3/2026 2:35 AM IDT)
• *Ankit Aggarwal (9/3/2026 2:15 PM IDT)
• *Daniel Bitin (10/3/2026 12:41 PM IDT)
• Christoph Baumgarten (10/3/2026 7:41 PM IDT)
• *Dieter Beckerle (11/3/2026 1:20 PM IDT)
• Florian Sikora (11/3/2026 5:27 PM IDT)
• Divyash (12/3/2026 6:37 AM IDT)
• Nadir HAMOU (12/3/2026 12:03 PM IDT)
• Lorenz Reichel (12/3/2026 4:35 PM IDT)
• *Hubert Puszklewicz (13/3/2026 3:19 PM IDT)
• Hakan Summakoğlu (14/3/2026 6:32 PM IDT)
• *Mark Zhu (14/3/2026 11:33 PM IDT)
• Vladimir Volevich (18/3/2026 2:06 PM IDT)
• *Sanandan Swaminathan (19/3/2026 2:34 AM IDT)
• *Nyles Heise (20/3/2026 4:14 AM IDT)
• *Naftali Peles (22/3/2026 3:21 AM IDT)
• Shirish Chinchalkar (23/3/2026 12:38 AM IDT)
• *Jackson La Vallee (27/3/2026 11:09 PM IDT)
• *Motty Porat (28/3/2026 2:52 AM IDT)
• *Nickita (28/3/2026 10:59 PM IDT)
• *Chris Shannon (30/3/2026 2:24 PM IDT)
• David Greer (31/3/2026 6:24 PM IDT)
• *David F.H. Dunkley (1/4/2026 4:19 AM IDT)
• *Armin Krauss (2/4/2026 6:51 PM IDT)
• Karl D’Souza (5/4/2026 1:47 AM IDT)
• Evan Semet (5/4/2026 6:50 AM IDT)
• Li Li (6/4/2026 7:59 AM IDT)
• *Fakih Karademir (7/4/2026 2:12 AM IDT)
• Govind Jujare (8/4/2026 1:50 PM IDT)
• Marco Bellocchi (8/4/2026 2:21 PM IDT)