Magnetic Tower of Hanoi facts for kids
The Magnetic Tower of Hanoi (MToH) puzzle is a fun twist on the classic Tower of Hanoi puzzle. Imagine each disk has two different colored sides, like "red" and "blue." The main goal is still to move all the disks from one pole to another. But here's the cool part: when you move a disk, you have to flip it over! Also, you can't place two disks on top of each other if their touching sides are the same color. This is because the disks actually have magnets inside them that stop you from making a wrong move!
The original Tower of Hanoi puzzle is linked to the number 2. For example, if you have n disks, the fewest moves needed is 2n − 1. But the Magnetic Tower of Hanoi is more complex and is actually related to the number 3!
Contents
How the Puzzle Started
Similar puzzles to the Magnetic Tower of Hanoi have been around for a while. For instance, a puzzle like one of the MToH's colored versions showed up in a math book called Concrete Mathematics. In that puzzle, you could only move disks between certain poles, which is a bit like having poles with fixed colors.
The main version of the MToH, where the poles don't have fixed colors, first appeared online around the year 2000. It was called "Domino Hanoi" back then. A mathematician named Fred Lunnon reviewed many different Tower of Hanoi puzzles, and this one was part of his review.
However, the MToH was also invented on its own by a physicist named Uri Levy in 1984. He came up with the name and the idea of using magnets. Dr. Levy later wrote several papers explaining the math behind the MToH.
Understanding the Puzzle
The MToH puzzle has three poles: a starting pole (Source or S), a finishing pole (Destination or D), and a middle pole (Intermediate or I). You also have n disks, all different sizes. Each disk has a Red side and a Blue side.
At the start, all the disks are stacked on the Source pole, from largest at the bottom to smallest at the top. All the disks have their Red side facing up.
The main goal is to move the entire stack to the Destination pole. The disks must still be in order from largest to smallest, but this time, all their Blue sides should be facing up!
Here are the rules for moving the disks:
- You can't put a bigger disk on top of a smaller disk. This is the same as the original Tower of Hanoi.
- When you move a disk, you must flip it over. So, if its Red side was up, now its Blue side will be up.
- You cannot place two disks together if their touching sides are the same color. For example, if a disk has its Blue side facing down, you can't put it on a disk that has its Blue side facing up. The magnets stop this!
Solving the Puzzle: Examples
Let's look at how to solve the MToH for a small number of disks. This helps us understand the rules better.
For 2 disks (n = 2), you need 4 steps. The original Tower of Hanoi with 2 disks only needs 3 steps. The extra step in MToH is needed because you have to flip the disks and make sure the colors match. Sometimes, you need an extra move just to flip a disk so it can be placed correctly.
For 3 disks (n = 3), the solution takes 11 steps. Here's a simplified idea of the steps:
- First, you move the two smaller disks (disks 2 and 3) from the Source pole to the Intermediate pole. This takes 4 moves, similar to the 2-disk puzzle.
- Then, you move the largest disk (disk 1) from the Source pole to the Destination pole. This is 1 move.
- Now, things get tricky because the poles are "colored" by the disks on them. The Destination pole now has disk 1 on it, so it's "blue." This means any disk placed on it must have its Blue side facing up.
- You then move disk 3 from the Intermediate pole to the Destination pole, going through the Source pole. This takes 2 moves.
- Next, move disk 2 from the Intermediate pole to the Source pole (1 move).
- Then, move disk 3 from the Destination pole to the Intermediate pole (1 move).
- Move disk 2 from the Source pole to the Destination pole (1 move).
- Finally, move disk 3 from the Intermediate pole to the Destination pole (1 move).
As you can see, solving the MToH is more complicated than the original Tower of Hanoi. You can't just repeat smaller solutions easily because of the color rules.
Different Colored Puzzles
The puzzle we've talked about so far is the "free" MToH. This means the poles themselves don't have a fixed color. An empty pole can accept a disk with either its Red or Blue side facing up.
But there are other versions where the poles *do* have fixed colors! If a pole is "pre-colored" Red, you can only place disks with their Red side facing up on it. The same goes for Blue poles.
These different versions are named with a 3-letter code like "SID," where S, I, and D stand for the Source, Intermediate, and Destination poles. R means Red, B means Blue, and N means Neutral (no color). So, the "NNN" puzzle is the free MToH we've been discussing. An "RBB" puzzle means the Source pole is Red, and the Intermediate and Destination poles are Blue.
These colored versions are important because when you play the free MToH, the poles become "colored" as you place disks on them. For example, if you place a disk with its Blue side up on a pole, that pole now acts like a "blue" pole. This means only other disks with their Blue side up can be placed on it.
Puzzle Similarities
Not all these colored puzzles are completely different. Some are actually the same because of symmetry. For example, solving the RBB puzzle backward is like solving the RRB puzzle forward (if you swap the colors). This means they are "time reversal symmetry" pairs. They need the same number of moves, even if the steps are different.
Finding Solutions
Just like the classic Tower of Hanoi, one of the best ways to solve the MToH is by using recursive algorithms. This means you break down a big problem into smaller, similar problems.
For example, for the RBB and RRB puzzles (the simplest colored ones), the steps to solve them for n disks often involve solving the same puzzle for n-1 disks.
Here's a simplified idea of how the RBB puzzle is solved:
- Move the n-1 smallest disks from the Source pole to the Intermediate pole using the RBB algorithm for n-1 disks.
- Move the largest disk (disk 1) from the Source pole to the Destination pole.
- Move the n-1 disks from the Intermediate pole to the Source pole using the RRB algorithm for n-1 disks.
- Move the n-1 disks from the Source pole to the Destination pole using the RBB algorithm for n-1 disks.
This shows how solving one puzzle depends on solving a slightly smaller version of itself, and sometimes even a different colored version!
How Many Moves?
Once we have these solving steps, we can figure out how many moves are needed. For the RBB and RRB puzzles, the total number of moves for n disks is given by a formula that involves 3n. This is a big difference from the classic Tower of Hanoi, which uses 2n. This means the MToH puzzle gets much harder, much faster, as you add more disks!
For example, the number of moves for the RBB puzzle is about half of 3n. And the number of times a specific disk k moves is 3k-1.
All versions of the MToH puzzle follow this pattern, where the number of moves grows roughly as 3n.
Images for kids
-
This image shows how the number of moves changes for different MToH puzzles.
