There's a game, called Towers of Hanoi. The basic idea is that you have a bunch of disks of varying thickness, and with holes in the middle, and you start with them stacked on a central pole, and you move them to another pole. You can only move one disk at a time, and you must never place a disk on a smaller disk. There are three pegs.
Here's a sample game. The numbers after each row will be explained later.
| | |
= | |
=== | |
===== | |
---+-----+-----+--- 000
| | |
| | |
=== | |
===== | =
---+-----+-----+--- 001
| | |
| | |
| | |
===== === =
---+-----+-----+--- 010
| | |
| | |
| = |
===== === |
---+-----+-----+--- 011
| | |
| | |
| = |
| === =====
---+-----+-----+--- 100
| | |
| | |
| | |
= === =====
---+-----+-----+--- 101
| | |
| | |
| | ===
= | =====
---+-----+-----+--- 110
| | |
| | =
| | ===
| | =====
---+-----+-----+--- 111
Now, here's the interesting part. It takes seven moves to solve this, for a total of eight positions including the starting state. There are three disks. In fact, for N disks, it always takes 2^N-1 moves to solve the puzzle. So, if you start with all disks on the left peg, and end with all disks on the right peg, you have 2^N stages, represented by N things. Since there's always exactly one correct move, there's a set of 2^N possible circumstances in which the disks can be.
This suggests that this is a particularly beautifully inefficient way to represent numbers. Now, the question is... Given a set of disks which we are assured is some portion of the way through a game of Towers of Hanoi, how many moves have we taken? If we can find a way to describe the positions as corresponding to numbers, we can count easily.
Here is the way to do it. Begin with the largest disk. If it is in the correct position, write down a 1. If it is not, write down a 0. Now, for each smaller disk, if it is on top of the previous disk, write down the number you just wrote down, and if it is not, write down the other number.
When you're done, you have the current move number encoded in binary, as illustrated in the picture above.
This is an interesting example of a coding where adding or subtracting one from a number only involves moving one thing. You'll note that a single piece moved can change all three bits of the binary representation. Fun, huh?
Comments [archived]
From: Shivering Timbers
Date: 2005-01-13 09:51:58 -0600
Hey, that’s pretty awesome! I have a 16-disk Tower of Hanoi set sitting around, and I’ve always wanted to use it for encoding UTF-16!
From: Goliath
Date: 2005-01-13 15:51:26 -0600
[does a bit of scribbling…]
Huh, yeah that’s correct. Neat! I hadn’t considered that before. Thanks, seebs.