Ponder This Challenge - August 2025 - A grid-cutting game

Alice and Bob play the following game: Given a grid of $a\times b$ squares, if it is Alice's turn, she uses vertical cuts to split the grid into two or more grids of the same size; if it's Bob's turn, he does the same with horizontal cuts. The cuts can be performed only on the edges of the grid squares, not on the squares themselves.

For example, given a $4\times 6$ grid, Alice has three possible moves that can split the grid into two $3\times 2$ grids, three $4\times 2$ grids, or six $4\times 1$ grids. Bob can either create two $2\times 6$ grids or four $1\times 6$ grids:

In the general game, Alice and Bob alternate turns. There can be several grids in play at once, and during each turn, the player chooses a grid and cuts it according to the above rules, replacing the grid with their newly created ones. A player loses if it’s their turn and they cannot cut any grid. For example, if the game consists of four $1\times 6$ grids and it's Bob's turn, Bob loses since he has no move that will split an existing grid into two or more grids.

We assume that Alice and Bob play optimally. Since this game satisfies the conditions of Zermelo's theorem, we can state with confidence that a player will win or lose given the position and that player’s method of play.

In the case of a single $1\times 1$ grid, it's obvious that whichever player starts, loses. That's also true for any $n\times n$ grid. We give the following definition: A position in the game has the value 0 if whichever player starts, loses.

For the case of a $1\times 2$ grid, it's obvious that if Bob starts, he loses, but if Alice starts, she wins since there is one move available to her, after which the game goes to a position of two value-0 grids. In this case, we say the $1\times 2$ grid has the value 1. Since adding a $2\times 1$ grid to the game with a $1\times 2$ grid "evens out" the game so that whoever starts by definition loses, we say the $2\times 1$ grid has the value $-1$.

It can be verified that given a $2\times 8$ grid, Alice wins whether she starts or not, and she still wins even if the game has two additional $2\times 1$ grids. But if the game has three $2\times 1$ grids, then the rule reverts back to whoever starts the game, loses. Since the value of each $2\times 1$ grid is $-1$ and there are three of them, we say that the value of the $2\times 8$ grid is 3.

In general, the value of an $r\times c$ grid, denoted $f(r,c)$, is

1. 0 if whoever starts the game loses.

2. $n$ (for $n\in\mathbb{N}$) if after adding $n$ $2\times 1$ grids to the game, whoever starts the game loses.

3. $-n$ (for $n\in\mathbb{N}$) if after adding $n$ $1\times 2$ grids to the game, whoever starts the game loses.

Your goal: Find the value of $f(a,b)$ for

A bonus "*" will be given for finding the value of $f(a,b)$ for

Solution

• Click here to view the solution

  August 2025 Solution:

  The solutions for the main and bonus question are

  6608
  16904
  

  This riddle touches upon the fascinating subject of combinatorial game theory, which is presented in a delightful manner in the book "Winning Ways for Your Mathematical Plays " by Berlekamp, Conway and Guy, which also includes the game presented in the riddle (referred to as "Maundy Cake") and credits Patrick Mauhin for its invention and solution. The numbers in the riddle were chosen such that a general knowledge of computing the value of a game (an interesting and non-trivial problem by itself, explained in great detail in the book) suffices for the main riddle, but for the bonus a more problem- specific solution is required.

  The method is as follows: given a number $n$ we can form a chain $n, n_1, n_2,\ldots,1$ where every number is obtained from the previous one by dividing it by its smallest prime factor. For example, if $n=630$ we obtain the chain $630, 315, 105, 35, 7, 1$.

  Now, given a $a\times b$ grid form the chains for $a,b$. If the chains are of equal length, the value of the game is 0. Otherwise, in the longer chain, sum the surplus values.

  For example, if $a=630$ while $b=75$, we obtain the chains

  630, 315, 105, 35, 7, 1
  75, 15, 1
  

  Thus Alice wins, with value $-(35+7+1)=-43$. The chains are easy to compute given the factoring of $a,b$; in this riddle, the factors were chosen among the first 2,000 primes to make brute-force factoring feasible.

Solvers

• *Lazar Ilic (31/7/2025 11:41 AM IDT)
• *Bertram Felgenhauer (31/7/2025 5:11 PM IDT)
• *Bobika Bo (31/7/2025 5:33 PM IDT)
• *Sanandan Swaminathan (1/8/2025 3:44 AM IDT)
• *Guangxi Liu (1/8/2025 8:32 AM IDT)
• Paul Revenant (1/8/2025 4:02 PM IDT)
• *King Pig (2/8/2025 6:05 AM IDT)
• *Reiner Martin (3/8/2025 12:45 AM IDT)
• *Matej Rebro & Elias Krainer (3/8/2025 2:53 PM IDT)
• *Vladimir Volevich (4/8/2025 9:34 AM IDT)
• *John Tromp (4/8/2025 4:32 PM IDT)
• *Charles Pombet (5/8/2025 10:24 PM IDT)
• *Liubing Yu (6/8/2025 6:44 AM IDT)
• *Radu-Alexandru Todor (6/8/2025 12:23 PM IDT)
• *Alex Teich (6/8/2025 6:08 PM IDT)
• *Camden Chappelle (6/8/2025 6:53 PM IDT)
• *Dan Dima (6/8/2025 11:34 PM IDT)
• *Shirish Chinchalkar (7/8/2025 2:56 AM IDT)
• *Daniel Bitin (8/8/2025 3:10 PM IDT)
• *Loukas Sidiropoulos (8/8/2025 8:21 PM IDT)
• *Prashant Wankhede (9/8/2025 6:12 AM IDT)
• *Alper Halbutogullari (9/8/2025 3:14 PM IDT)
• *Peter Moser (9/8/2025 8:51 PM IDT)
• *Stephen Ebert (9/8/2025 11:54 PM IDT)
• *Lorenz Reichel (10/8/2025 2:44 PM IDT)
• *Robert Berec (10/8/2025 5:14 PM IDT)
• *Todd Will (12/8/2025 1:07 AM IDT)
• *Motty Porat (12/8/2025 9:21 PM IDT)
• *Dwij Mehta (13/8/2025 6:43 AM IDT)
• *Jordan Payette (13/8/2025 3:21 PM IDT)
• *Tim Walters (13/8/2025 8:37 PM IDT)
• *Paul Lupascu (14/8/2025 3:20 PM IDT)
• Nadir S. (18/8/2025 3:56 PM IDT)
• Shouky Dan & Ganor Tamir (20/8/2025 10:24 PM IDT)
• *Govind Jujare & Hansraj Nahata (21/8/2025 11:25 PM IDT)
• *Joydeep Paul (22/8/2025 2:13 AM IDT)
• *Kang Jin Cho (23/8/2025 5:25 AM IDT)
• *David F.H. Dunkley (25/8/2025 12:12 AM IDT)
• *Daniel Chong Jyh Tar (25/8/2025 6:26 AM IDT)
• *Ananda Raidu (26/8/2025 4:48 PM IDT)
• *Daniel Copeland (27/8/2025 6:04 PM IDT)
• *Marco Bellocchi (29/8/2025 1:16 AM IDT)
• *Murali P Nair & Nirmal Govindaraj (29/8/2025 8:11 PM IDT)
• Ankit Chakraborty (30/8/2025 3:00 AM IDT)
• *Haoyu Sun (30/8/2025 4:12 AM IDT)
• David Greer (1/9/2025 5:46 PM IDT)
• Bin Xiao (3/9/2025 7:44 AM IDT)
• *Evan Semet (4/9/2025 11:14 AM IDT)
• *Steffen Wolf (4/9/2025 6:09 PM IDT)
• *Jackson La Vallee (5/9/2025 6:27 AM IDT)
• Li Li (5/9/2025 6:41 AM IDT)