Solving the Towers of Hanoi by Counting in Binary

ZUSAMMENFASSUNG

In 30 Sekunden

3Blue1Brown and Keith Schwarz connect binary counting to the Towers of Hanoi. They show the move rule, explain its recursive structure and derive the minimum of 2ⁿ−1 moves for n disks; a later video covers the connection to Sierpiński’s triangle.

1Three pegs and disksMove one disk at a time and never place a larger disk on a smaller one.
2Binary carriesBits represent powers of two and roll over as counting advances.
3A counting ruleThe position reached by a carry determines which disk moves.
4The recursive moveMove the smaller stack away, move the large disk, then replace the stack.
5The minimumThe recurrence T(n)=2T(n−1)+1 yields 2ⁿ−1 moves.

Das Wichtigste

A binary increment selects a disk according to the position reached by its carry.
The smallest disk cycles through the pegs, and each larger disk has a forced legal move.
Moving a large disk requires moving the smaller stack away and then back.
The three-peg puzzle needs at least 2ⁿ−1 moves for n disks, and the recursive solution achieves that bound.
Binary counting and the Hanoi solution share the same recursive structure.

ThemenMathematics

VOLLTEXT

Den bearbeiteten Text nach Kapiteln lesen

Transkript zeigen

Nur das Transkript

The Hanoi puzzle

The presenters define the three-peg puzzle and its legal moves.

The Towers of Hanoi can be solved by following the rhythm of binary counting. In this first part, the presenter and former computer-science lecturer Keith Schwarz explain the puzzle and the recursive structure behind the connection; a follow-on video explores Sierpiński’s triangle.

The puzzle has three pegs and disks of different sizes stacked largest to smallest. The aim is to move the whole stack to another peg, moving one disk at a time and never placing a larger disk on a smaller one.

FOLIE 1 / 4The initial five-disk towerDisks are numbered from smallest to largest, starting at zero.

The example labels the smallest disk 0, then 1, 2 and so on. The first move must be disk 0. Once it has moved, disk 1 cannot go on top of it, so its destination is the remaining peg.

The rhythm of binary

Counting in base two reveals a self-similar pattern of carries.

Schwarz’s observation is that the pattern of binary counting determines which disk to move. To see why, first look at the rhythm of carrying in an ordinary positional number system.

In base ten we cycle through digits 0 to 9, then reset the ones place and carry into the tens place. After enough repetitions, the tens place also rolls over and the hundreds place advances. The same pattern repeats at larger scales.

Binary uses only 0 and 1. After 0 and 1, the next number is written 10: one group of two and zero ones. Then 11 represents three; adding one again yields 100, or one group of four.

Binary place values are powers of two: ones, twos, fours, eights and so forth. Carries happen frequently, making the repeated structure especially visible.

At each scale, binary counting has the same shape: count through a smaller range, carry into the next place, then repeat that smaller pattern. For instance, reaching 1111 involves counting the last three bits up, carrying into the eights place and counting them up again.

Turn binary carries into moves

Each carry selects a disk, while the smallest disk cycles through the pegs.

Begin counting in binary from zero. Whenever the increment flips only the final bit, move the smallest disk one peg to the right, wrapping from the rightmost peg back to the first. This fixed direction determines which of the other pegs receives the finished tower; reversing the direction selects the other destination.

FOLIE 3 / 4The smallest disk and the last bitFlipping only the last bit corresponds to moving disk 0.

When a carry reaches the twos place, move disk 1. It has only one legal destination other than the peg holding disk 0. A carry to the fours place calls for disk 2, a carry to the eights place calls for disk 3, and so on.

The resulting sequence starts 0, 1, 0, 2, 0, 1, 0, 3. The rule looks surprising: why is the indicated larger disk free whenever the corresponding carry occurs, and why does the process finish efficiently?

Why recursion gives the minimum

Moving the largest disk requires solving the smaller problem before and after it.

Schwarz explains the recursive viewpoint. To move a large disk to its destination, all smaller disks must first be stacked on the spare peg. Move the large disk once, then move that smaller stack onto it.

FOLIE 4 / 4Move the smaller stack firstThe larger disk can move only after all smaller disks occupy the spare peg.

The smaller stack is the same kind of problem on fewer disks. Each disk follows the same pattern: move the disks above it away, move the disk, then put the smaller stack back on top.

The reasoning also establishes optimality. Before the largest disk can move, every smaller disk must be moved away; afterward, every smaller disk must be moved onto it. If T(n) is the minimum number of moves, T(n)=2T(n−1)+1 with T(0)=0, giving T(n)=2ⁿ−1.

Why the patterns match

Binary increments and the recursive solution share the same structure.

Binary counting mirrors this recursion: complete the smaller pattern, carry into the next bit, and complete the smaller pattern again. The disk moved at each step corresponds to the highest bit changed from 0 to 1 by the increment.

For two disks, the sequence is disk 0, disk 1, disk 0, matching the pattern of binary increments up to 11. For three disks, solve the two-disk problem, move disk 2 and solve the two-disk problem again, matching the larger binary pattern.

At every scale, both processes have the structure “subproblem, one step, subproblem.” Looking at the bits that change therefore lets us reconstruct the recursive Hanoi algorithm. The promised connection to Sierpiński’s triangle is left for part two.