Ponder This Challenge - August 2026 - The Wheel of Buttons

The Wheel of Buttons

This puzzle was suggested by Sanandan Swaminathan - thanks!

A game show is arranged as follows: The main attraction is a wheel that has $N$ buttons equidistant from one another, such that the wheel looks perfectly symmetric.

Each button has two possible states: "on" and "off". There's no indicator to the status of a button, and each press toggles between those two states ("on" -> "off" -> "on" and so forth). At the beginning of the game, the buttons have random states with the one condition that not all buttons are "on".

On each turn, the wheel spins randomly without the contestant looking; the buttons are marked with $1,2,\ldots$ beginning at the top-left button and going clockwise. The contestant picks a subset of the buttons and pushes them. After the contestant is done, two things can happen:

1. If all the buttons are "on", the contestant wins; this is made clear with balloons and confetti.
2. If not all the buttons are "on", a new round begins. Again, the wheel is spun without the contestant seeing it.

The contestant's goal is to find a strategy that guarantees winning in the least number of rounds, even if the game cheats and the spins of the wheel are not random.

The choices of the contestant can be described by a sequence of natural numbers. Rounds are separated by 0, and each round contains the numbers of the buttons pressed by the contestant.

For example, the following is an optimal solution for the case $N=2$:

If both buttons were "off" at the beginning, the game is won after the first round. Otherwise, after the second round both buttons have the same state, so after the third round, the contestant has certainly won the game.

Summing up the numbers in the solution, we arrive at the value $7$. If, in the middle round, we would have used 2 instead of 1, we'd reach the value $8$. We are interested in the minimum value that can be obtained from an optimal solution: We call this the "optimal solution sum" for $N$.

Your goal: Find the optimal solution sum for $N=8$.

A bonus "*" will be given for finding the optimal solution sum for $N=64$.

Solution

• Click here to view the solution

  Solution

  The numerical solutions are:

  • n = 8: 6279
  • n = 64: 27636190239652591799943

  Solving the game by hand for $n=4$ is a good way to obtain a feel to the way a general solution works. Encode each state of the table as an element of $\mathbb{F}_2^4$, i.e. a sequence of 0 and 1 of length 4 (let 1 denote an off switch so that the goal is to reach $0000$). At each step we maintain a set $A$ of the states we know the table cannot be in. At the beginning, $A={0000}$.

  At each turn, if we model our presses as a binary sequance $a$ (where 0 is "no click" an 1 is "click"), the first of all $A\leftarrow A+a=\left\{x+a\ |\ x\in A\right\}$. If we choose $a$ wisely, it will be equal to a state not present in $A$, and this will result in either winning the game or adding $0000$ to $A$, and a wise choice of $a$ would guarantee that at this stage, $A$ is closed to rotations, otherwise we'll lost some of its elements and won't be able to achieve and optimal solution. This forces the first few steps to be:

  1. $a=1111$ and then $A=\left\{0000, 1111\right\}$
  2. $a=1010$ and then $A=\left\{0000, 1010, 0101\right\}$
  3. $a=1111$ and then $A=\left\{0000, 1010, 0101, 1111\right\}$
  4. $a=1100$ and then $A=\left\{0000,1100,0011,0110,1001\right\}$

  The pattern that emerges is intuitively this: Each element of $\mathbb{F}_2^4$ has some "degree of symmetry" (which will be precisely defined later), with $1111$ being on top, afterwards $1010$ and $0101$, then $1100, 0110, 0011,1001$ and so on. If we denote the degree of symmetry of $a$ by $\nu(a)$ with $\nu(1111)=3$, we have in general $2^{4-1-d}$ elements of degree of symmetry $d$ (also denote $\nu(0000)=\infty$).

  The main result about the degree of symmetry is that if $\nu(a) < \nu(x)$ for all $x\in A$ then all the elements of $A+a$ would have degree $\nu(a)$. Also observe that the set of all elements of a specific degree of symmetry is closed under rotations. So a valid strategy (which can be shown to be optimal) is this: First make $A$ contain all the elements of degree higher than $k$, then add the least costly element of degree $k$. Since the number of all elements of degree $>k$ is equal to the number of elements of degree $k$ (when $N$ is a power of 2), and since adding an element is bijective, this ensures we'll end up with the set of all elements of degree $k$, and then proceed recursively since adding elements of degree higher than $k$ won't affect the elements of degree $k$.

  The same thing can be done for a general $N$ which is a power of 2, not only for $N=4$.

  For a precise definition of $\nu$, one can consider the ring $R=\mathbb{F}_2[x]/(x^N-1)$, where we think of the elements of a table state as the coefficients of the polyonmials. A beneficial property of this ring is that multiplication by $x$ is the same as a single rotation of the state, thus converting a combinatorial problem into an algebric one. In this ring, denote $y=x+1$. Now, every element of $R$ can be uniquely represented as $y^dp(y)$ where $p(1)=1$ (i.e. the element is a polynomial whose monom of minimal degree is $y^d$). Then $d$ is the $\nu$ for that element (it remains to prove all the nice properties of $\nu$ hold).

Solvers

• *Daniel Chong Jyh Tar (31/7/2026 4:54 PM IDT)
• *Jean-François Hermant (31/7/2026 5:28 PM IDT)
• Ashfaque Shaikh (31/7/2026 5:45 PM IDT)
• Alex Fleischer (31/7/2026 7:18 PM IDT)
• *Prashant Wankhede (31/7/2026 7:31 PM IDT)
• *Stéphane Higueret (31/7/2026 7:34 PM IDT)
• *Bertram Felgenhauer (31/7/2026 8:39 PM IDT)
• *Juergen Koehl (31/7/2026 9:51 PM IDT)
• *Paul Lupascu (31/7/2026 9:57 PM IDT)
• *King Pig (31/7/2026 10:38 PM IDT)
• *Dan Dima (1/8/2026 1:23 AM IDT)
• *Alper Halbutogullari (1/8/2026 2:16 AM IDT)
• *Jack Saleeby (1/8/2026 3:08 AM IDT)
• *Kang Jin Cho (1/8/2026 3:32 AM IDT)
• *Steffen Wolf (1/8/2026 4:48 PM IDT)
• *Rahid Zaman (1/8/2026 6:48 PM IDT)
• *Rethna Pulikkoonattu (2/8/2026 3:41 AM IDT)
• *Carter Tran (3/8/2026 9:49 AM IDT)
• Nadir S. (3/8/2026 11:01 AM IDT)
• *Lazar Ilic (3/8/2026 8:20 PM IDT)
• *Patricia Ji (4/8/2026 4:34 AM IDT)
• *Guangxi Liu (4/8/2026 5:10 AM IDT)
• *Jackson La Vallee (4/8/2026 6:29 AM IDT)
• *Tamir Ganor & Shouky Dan (4/8/2026 11:28 AM IDT)
• *Siamak Alimirzazadeh (4/8/2026 12:15 PM IDT)
• *Latchezar Christov (4/8/2026 2:10 PM IDT)
• *Franciraldo Cavalcante (4/8/2026 3:08 PM IDT)
• *Giorgos Kalogeropoulos (4/8/2026 5:46 PM IDT)
• *Abhishek Sekar (4/8/2026 6:01 PM IDT)
• *Vladimir Volevich (5/8/2026 3:39 PM IDT)
• George Jiri Spitalsky (5/8/2026 8:24 PM IDT)
• *Kevin Yu (5/8/2026 10:12 PM IDT)
• *Henk Waßmann (5/8/2026 11:09 PM IDT)
• Mark Buisseret (6/8/2026 8:40 AM IDT)
• Amos Guler (6/8/2026 7:30 PM IDT)
• *Evan Semet (6/8/2026 9:21 PM IDT)
• *Dominik Reichl (6/8/2026 10:51 PM IDT)
• *Fakih Karademir (7/8/2026 4:00 PM IDT)
• *Sullivan Hart (7/8/2026 6:38 PM IDT)
• Baocheng Jiao (8/8/2026 1:10 AM IDT)
• *Aayaam Panigrahi (8/8/2026 9:12 AM IDT)
• Ahmet Yüksel (8/8/2026 12:51 PM IDT)
• Sakib (8/8/2026 1:33 PM IDT)
• *Harold Gutch (8/8/2026 2:27 PM IDT)
• *Evert van Dijken (9/8/2026 11:05 AM IDT)
• Resnina Tathyana (9/8/2026 11:31 PM IDT)
• *Justin Mazenauer (10/8/2026 12:34 PM IDT)
• *John Tromp (10/8/2026 9:54 PM IDT)
• *Peter Moser (10/8/2026 10:39 PM IDT)
• *Paulo Sousa (11/8/2026 2:19 AM IDT)
• *Sven Schneider (11/8/2026 2:58 AM IDT)
• *Daniel Bitin (12/8/2026 12:58 AM IDT)
• Shirish Chinchalkar (12/8/2026 2:59 AM IDT)
• *Lawrence Hon (12/8/2026 6:22 AM IDT)
• *Lucas Reymond (12/8/2026 1:22 PM IDT)
• *Tongyang Song (12/8/2026 4:23 PM IDT)
• Pataki Gida (13/8/2026 1:19 AM IDT)
• *Jason Shaw (14/8/2026 12:23 AM IDT)
• *Martin Thorne (14/8/2026 12:28 AM IDT)
• *Peter Ji (14/8/2026 5:39 AM IDT)
• *Hakan Summakoğlu (15/8/2026 12:38 AM IDT)
• *Parth Rana (16/8/2026 7:47 AM IDT)
• *Nickita Khylkouski (16/8/2026 8:10 PM IDT)
• *Karl D’Souza (16/8/2026 11:52 PM IDT)
• *Emek Can Doğru (17/8/2026 9:58 AM IDT)
• *Dieter Beckerle (17/8/2026 10:45 AM IDT)
• *Lorenz Reichel (17/8/2026 4:04 PM IDT)
• Danny Tang (18/8/2026 12:41 AM IDT)
• *Stephen Ebert (18/8/2026 3:48 AM IDT)
• Hansraj Nahata (19/8/2026 4:00 AM IDT)
• Jim Clare (20/8/2026 11:50 PM IDT)
• *Naftali Peles (21/8/2026 3:33 AM IDT)
• Paul Revenant (21/8/2026 2:44 PM IDT)
• Max Best (21/8/2026 9:36 PM IDT)
• *Ludwig Schulz (23/8/2026 12:42 AM IDT)
• *Anant Chebiam (23/8/2026 8:22 AM IDT)
• Purin Williams (24/8/2026 10:43 AM IDT)
• *Krish Desai (24/8/2026 10:02 PM IDT)
• *Reda Kebbaj (25/8/2026 4:26 AM IDT)
• *Florian Fischer (25/8/2026 8:21 PM IDT)
• Alok Menghrajani (26/8/2026 11:09 AM IDT)
• Puvichakravarthy Ramachandran (26/8/2026 10:32 PM IDT)
• *Michele Missiroli (26/8/2026 11:11 PM IDT)
• *Motty Porat (27/8/2026 3:05 AM IDT)
• *Björn Nerbe (27/8/2026 4:31 PM IDT)
• *Rajesh Sathiyanarayanan (28/8/2026 4:10 PM IDT)
• *Haoyi Zhang (29/8/2026 1:35 PM IDT)
• Liubing Yu (30/8/2026 12:49 AM IDT)
• *David F.H. Dunkley (30/8/2026 2:45 AM IDT)
• Gary M. Gerken (30/8/2026 6:15 AM IDT)
• *Sanandan Swaminathan (30/8/2026 12:56 PM IDT)
• *Erik Wünstel (31/8/2026 10:19 PM IDT)
• *Alexander Bielik (1/9/2026 1:23 AM IDT)
• Nyles Heise (1/9/2026 4:20 AM IDT)
• *Karl Mahlburg (1/9/2026 10:08 PM IDT)
• *Lyes Belhoul (3/9/2026 3:10 PM IDT)
• *David Greer (9/9/2026 1:22 PM IDT)
• *Marco Bellocchi (9/9/2026 5:59 PM IDT)
• Matt Cristina (13/9/2026 12:52 AM IDT)
• *Li Li (21/9/2026 6:06 PM IDT)
• *Aditya Bhoj (22/9/2026 12:04 AM IDT)