Ponder This Challenge - April 2024 - Simultaneous Towers of Hanoi

The Tower of Hanoi game consists of three rods and $n$ disks of different sizes (denoted by $1,2,\ldots,n$) that can slide onto any rod. The initial state of the game consists of all the disks on one rod in ascending order, with disk $1$, the smallest and lightest of the disks on top.

Each move in the game consists of choosing one rod, picking up the top disk from that rod, and placing it on another rod. Such a move is allowed only if the disk being moved is smaller than the top disk on the target rod, or if the target rod is empty.

If the three rods are placed on different points on a circle, at any given state, there are three possible moves:

0. Take disk "1" from its rod and move it clockwise to another rod.
1. Take disk "1" from its rod and move it counterclockwise to another rod.
2. Take a disk which is not "1" and move it to another rod.

Move 2 will not always be available, such as when all the disks are currently located on one rod. In such instances, we say that Move 2 does nothing. In all other cases, there is only one legal way to perform Move 2.

We can describe the flow of games using a string describing moves. For example, "0202020", when performed on the initial state of a game with $n=3$, moves all the disks one rod clockwise. We call the state where all the disks are on the clockwise-located rod the winning state of the game. Another way to describe that game is with the string "02" which must be performed for exactly 7 steps, with the convention that once the end of the string is reached, we start over at the beginning. It can be shown that the $n$-disk game is won by using the string "02" for $2^n-1$ steps with $n$ odd, and "12" for $2^n-1$ steps with $n$ even.

For example, when $n=3$ and the move string is "0202112", after 8 steps the winning step is reached, and the next step does nothing, so we say the winning state is reached both on step 8 and step 9. Similarly, for $n=4$ and move string "200211", the winning state is reached after 41 and 122 moves. However, if we start two simultaneous games, one with $n=3$ and "0202112", and the other with $n=4$ and "200211", and perform each step in both games at the same time, both games will reach a winning state together for the first time after 932 steps.

Your Goal: For the two games defined by $n=7$ and "12021121120020211202121", and $n=10$ and "0211202112002", find the minimal number of steps at which both games reach a winning state at the same time.

A Bonus "*" will be given for finding the minimal number of steps such that both the above games and also the game defined by $n=9$ and "20202020021212121121202120200202002121120202 112021120020021120211211202002112021120211200212112020212120211" reach a winning state for the first time.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  April 2024 Solution:

  For the two-game question, the solution is 16511310.

  For the three-game question, the solution is 1169723214.

  An easy way to obtain theses solutions is analyizing each game by itself, identifing the number of steps needed to reach a winning state, and for each pair/triplet of steps number for the games, use the chinese remainder theorem to obtain the smallest number of steps giving the needed number of steps modulo the cycle length in each game.

Solvers

• *Yi Jiang (1/4/2024 11:20 PM IDT)
• *Paul Revenant (2/4/2024 12:03 AM IDT)
• *Victor Chang (2/4/2024 1:25 AM IDT)
• *Jingran Lin (2/4/2024 3:08 AM IDT)
• *Serge Batalov (2/4/2024 6:14 AM IDT)
• *Daniel Chong Jyh Tar (2/4/2024 7:30 AM IDT)
• *Lazar Ilic (2/4/2024 8:49 AM IDT)
• *Yan-Wu He (2/4/2024 9:29 AM IDT)
• *Sanandan Swaminathan (2/4/2024 9:40 AM IDT)
• *Alper Halbutogullari (2/4/2024 11:11 AM IDT)
• *Lorenz Reichel (2/4/2024 11:36 AM IDT)
• *Bertram Felgenhauer (2/4/2024 11:57 AM IDT)
• *Ralf Jonas (2/4/2024 2:46 PM IDT)
• *Guillaume Escamocher (2/4/2024 3:47 PM IDT)
• *Guglielmo Sanchini (2/4/2024 4:54 PM IDT)
• *Thomas Ilsche (2/4/2024 6:18 PM IDT)
• *Alex Izvalov (2/4/2024 6:47 PM IDT)
• *Bert Dobbelaere (2/4/2024 8:17 PM IDT)
• *Dieter Beckerle (2/4/2024 8:17 PM IDT)
• *John Tromp (2/4/2024 9:19 PM IDT)
• *Andrew Gauld (2/4/2024 9:35 PM IDT)
• *Paul Shaw (2/4/2024 10:57 PM IDT)
• *Reiner Martin (3/4/2024 12:23 AM IDT)
• *Giorgos Kalogeropoulos (3/4/2024 2:26 AM IDT)
• *Martin Thorne (3/4/2024 2:50 AM IDT)
• *Evan Schor (3/4/2024 3:49 AM IDT)
• *David Kelly (3/4/2024 6:56 AM IDT)
• *Gary M. Gerken (3/4/2024 7:26 AM IDT)
• *Vamsi Krishna Talupula (3/4/2024 10:05 AM IDT)
• *Wolfgang Kais (3/4/2024 1:27 PM IDT)
• *Michael Ciwinski (3/4/2024 2:29 PM IDT)
• *Amos Guler (3/4/2024 3:04 PM IDT)
• *Mark Pervovskiy (3/4/2024 3:12 PM IDT)
• *Latchezar Christov (3/4/2024 3:19 PM IDT)
• *Guilliou Robin (3/4/2024 5:12 PM IDT)
• Graham Hemsley (3/4/2024 6:08 PM IDT)
• *Clive Tong (3/4/2024 6:12 PM IDT)
• *Govind Jujare (3/4/2024 10:44 PM IDT)
• *Leon Rode (4/4/2024 12:53 AM IDT)
• *Phil Proudman (4/4/2024 2:16 AM IDT)
• *Joaquim Carrapa (4/4/2024 2:29 AM IDT)
• *Vladimir Volevich (4/4/2024 12:41 PM IDT)
• *Florian Sikora (4/4/2024 1:07 PM IDT)
• *Sri Mallikarjun J (4/4/2024 6:55 PM IDT)
• *Peter Moser (4/4/2024 10:21 PM IDT)
• *Cameron Ritson (5/4/2024 1:58 AM IDT)
• *Blaine Hill (5/4/2024 2:56 AM IDT)
• *Guang-Zhong Sun (5/4/2024 3:36 AM IDT)
• *Grant Boudreaux (5/4/2024 4:15 AM IDT)
• *Mark Mammel (5/4/2024 5:00 AM IDT)
• *Marco Bellocchi (5/4/2024 1:03 PM IDT)
• Karl D’Souza (5/4/2024 11:29 PM IDT)
• *Omer Ronen (6/4/2024 1:10 AM IDT)
• *Rudy Cortembert (6/4/2024 1:49 AM IDT)
• *Andrea Andenna (6/4/2024 2:08 AM IDT)
• *Dan Ismailescu (6/4/2024 2:43 AM IDT)
• *Ido Meisner (6/4/2024 3:25 PM IDT)
• *Fakih Karademir (6/4/2024 3:45 PM IDT)
• Adrian Neacsu (6/4/2024 8:01 PM IDT)
• *David Greer (6/4/2024 9:23 PM IDT)
• *Dezhi Zhao (6/4/2024 11:12 PM IDT)
• *Franciraldo Cavalcante (7/4/2024 3:55 AM IDT)
• Shelby Doolittle (7/4/2024 6:20 AM IDT)
• *Dwij Mehta (7/4/2024 8:35 AM IDT)
• *Ariel Erusalinsky (7/4/2024 1:50 PM IDT)
• *Harald Bögeholz (7/4/2024 7:48 PM IDT)
• *David F.H. Dunkley (7/4/2024 11:50 PM IDT)
• *King Pig (8/4/2024 1:22 AM IDT)
• *Guangxi Liu (8/4/2024 7:46 AM IDT)
• *Shouky Dan & Tamir Ganor (8/4/2024 9:31 AM IDT)
• *Sanjay Rao (8/4/2024 6:27 PM IDT)
• *Alain Michiels (8/4/2024 8:14 PM IDT)
• *Stéphane Higueret (8/4/2024 9:27 PM IDT)
• *Emmanuel Lazard (8/4/2024 9:44 PM IDT)
• *Arnold Yim (8/4/2024 10:45 PM IDT)
• *Alexander Marschoun (9/4/2024 1:48 AM IDT)
• *Ritesh Ranjan (9/4/2024 2:47 AM IDT)
• *Senthan Sivatharan (9/4/2024 7:01 AM IDT)
• *Michail Shatalov (9/4/2024 9:37 AM IDT)
• *Zoltan Haindrich (9/4/2024 7:09 PM IDT)
• *Wenjie Yang (10/4/2024 12:55 AM IDT)
• *Matt Cristina (10/4/2024 7:45 AM IDT)
• *Chris Shannon (10/4/2024 8:25 AM IDT)
• Fabio Michele Negroni (11/4/2024 7:11 PM IDT)
• *Gyozo Nagy (12/4/2024 12:07 AM IDT)
• *Wolfgang Glas (12/4/2024 1:17 AM IDT)
• *Hakan Summakoğlu (12/4/2024 6:14 PM IDT)
• *Jonas Oja (12/4/2024 9:44 PM IDT)
• *Teawoo Kim (13/4/2024 12:03 AM IDT)
• *Daniel Bitin (14/4/2024 9:18 PM IDT)
• *Justin Snopek (15/4/2024 10:20 PM IDT)
• *Abhinav Bana (16/4/2024 1:49 PM IDT)
• *Michael Liepelt (17/4/2024 1:50 PM IDT)
• *Nadir S. (17/4/2024 3:14 PM IDT)
• *Nivrutti Tambe (17/4/2024 7:07 PM IDT)
• *Nyles Heise (19/4/2024 6:02 AM IDT)
• *Evan Semet (19/4/2024 8:15 AM IDT)
• Shirish Chinchalkar (20/4/2024 12:56 AM IDT)
• *Sofia Kozlova (20/4/2024 1:08 PM IDT)
• *Kang Jin Cho (20/4/2024 6:40 PM IDT)
• *Karl Mahlburg (22/4/2024 3:04 AM IDT)
• *Christoph Baumgarten (23/4/2024 8:32 AM IDT)
• Noam Zaks (23/4/2024 1:40 PM IDT)
• *Motty Porat (24/4/2024 1:37 AM IDT)
• *Keith Kaplan (25/4/2024 4:35 AM IDT)
• *Dillon Davis (25/4/2024 5:22 PM IDT)
• *Benjamin Cha (27/4/2024 7:28 PM IDT)
• *Todd Will (27/4/2024 8:28 PM IDT)
• *Jason Kim (27/4/2024 8:58 PM IDT)
• *Tim Walters (27/4/2024 9:49 PM IDT)
• William Han (27/4/2024 10:20 PM IDT)
• *Murugesan Sadayandy (29/4/2024 7:27 AM IDT)
• *Avi Levin (30/4/2024 2:40 AM IDT)
• *Arvind Venkatesan (30/4/2024 3:00 AM IDT)
• *Jeffrey Curtis (30/4/2024 7:36 AM IDT)
• Paul Lupascu (30/4/2024 2:54 PM IDT)
• *Andreas Stiller (30/4/2024 4:22 PM IDT)
• *Daniel Copeland (30/4/2024 6:05 PM IDT)
• Garance Pontier (30/4/2024 9:50 PM IDT)
• *Walker Demel (30/4/2024 10:18 PM IDT)
• *Li Li (1/5/2024 2:56 PM IDT)
• *Noam Nisgav (3/5/2024 2:45 PM IDT)
• *Victoria Davydenko (3/5/2024 4:27 PM IDT)
• *Armin Krauss (3/5/2024 11:14 PM IDT)
• *Radu-Alexandru Todor (4/5/2024 1:26 PM IDT)
• *Dan Dima (5/5/2024 12:35 PM IDT)