Tower of Hanoi

I was chatting with my brother Porter the other day and he told me how he made a Tower of Hanoi game for his children to play with. It’s a fairly simple game with a well-known binary sequence to solving it, in fact it’s one of the few puzzle games where the God’s Algorithm (a shortest-number-of-moves algorithm that can be mathematically proven) exists and is known. The shortest-path solution takes exactly \(2^n-1\) moves to move the disks from one post to another. Porter mentioned in his next blog post that him and his son then calculated how high of a stack The Flash could do if he could move 1 million disks per second, and concluded that it would still take him longer than the age of the universe to complete the 100-disk version.

That’s a good start, but any self-respecting geek has to take things a notch further. First I needed to derive a formula that let’s me calculate how high of a stack I can complete in a given time given a rate of how many disks per second I can move. The original equation we can rearrange as:

\(\displaystyle{N=\frac{\ln (n+1)}{\ln 2}}\) ,

where N is the number of disks, and n is the number of moves. Then we can replace the n with \(n=\omega t\), where \(\omega\) is the frequency of number of moves per unit of time, and t is the total time. So now our equation is:
\(\displaystyle{N=\frac{\ln (\omega t)}{\ln 2}}\) .

You may notice that I have ignored the \(\small{+1}\). This is because the \(\omega t\) will be so large that we can ignore the the \(\small{+1}\), as it is inconsequential.

This formula let’s us do some basic calculations. If we take t to be the age of the universe in seconds (about \(\small{4.33\times 10^{17}s}\)) then we have the following number of disks we can expect to complete within that time for the given number of disks moved per second:

\(\begin{array}{cc} \omega ,s^{-1} & N,\text{disks} \\ \hline 1 & 58 \\ 10 & 61 \\ 100 & 65 \\ 1000 & 68 \\ 1\times 10^6 & 78 \\ 1\times 10^9 & 88\end{array}\)

So we can see that if an immortal Flash were to move disks for the entire age of the current universe at the rate of 1000 disks/s, then he could only expect to complete a stack of 68 disks. Increasing it to 1 billion disks/s only increases it to 88 disks! Still a far cry from completing 100 disks.

So the next question is what kind of energy/power requirement would we need to move the disks at these kind of rates? First we’ll need to make some assumptions on mass and distance. One typical move is shown in the animated gif below (if someone knows how to set it so that it will repeat more than once, please let me know):

In terms of mechanics, to move the disk from column one to column two the disk has to do six steps: 1) accelerate up until its halfway up the column, 2) decelerate until it comes to a stop having just cleared the column, 3) accelerate horizontally until its halfway to the next column, 4) decelerate until it comes to a stop above the new column, 5) accelerate down until it’s halfway down the new column, and finally 6) decelerate until it comes to a stop in the new position.

Now you may say that we don’t need to decelerate the disk as it reaches its resting point and just let it smack into the resultant stack, but when the speeds become really fast the energy will be enough to obliterate any disk, so we’ll include the final deceleration. We’ll also assume this is done in a vacuum so we can ignore wind resistance, otherwise the heat would be more than enough to ionize the disks (those that have read the well known Physics of Santa will be familiar with this). At some point the acceleration alone will become greater than the structural integrity of the disks, as well as relativistic effects at some point coming into play. We’ll get to those in a moment. For now though, we’ll simplify the 6 steps above by making them all the same length for every step. We can do this by putting the three columns in a triangular arrangement and then saying the disks are thin enough that we can neglect the change in the height of the stack as we make progress. We’ll say the columns are 10 cm apart and 10 cm high, so each of the 6 steps will be 5 cm. Also we’ll say each disk weighs 100 g.

Using classical mechanics (ignoring relativistic effects), the time to complete one step is simply 1/6 of a move, so that is:

\(\displaystyle{t=\frac{1}{6}\omega ^{-1}}\) .

The maximum velocity attained (so that we can know if we’re getting close to relativistic speeds) is:
\(\displaystyle{v_m=\frac{2L}{t}}\) .

The acceleration the disk undergoes (to see of we are overcoming structural integrity) is:
\(\displaystyle{a = \frac{2 L}{t^2}}\) .

The energy required to complete one step is:
\(\displaystyle{E=\frac{2m L^2}{t^2}}\) .

And finally the power required to keep the disks moving is:
\(\displaystyle{P=\frac{2m L^2}{t^3}}\) .

Putting all these together in a handy chart we can see the results.

\(\small{\begin{array}{ccccccc}\omega, s^{-1}& N & t_{step}, s & v_{\max},m/s & a,m/s^2 & E, J & P, W \\ \hline 1 & 58 & 1.67\times 10^{-1} & 0.6 & 3.6 & 1.8\times 10^{-2} & 0.108 \\ 10 & 61 & 1.67\times 10^{-2} & 6 & 360 & 1.8 & 108 \\ 100 & 65 & 1.67\times 10^{-3} & 60 & 3.6\times 10^4 & 180 & 1.08\times 10^5 \\ 1000 & 68 & 1.67\times 10^{-4} & 600 & 3.6\times 10^6 & 1.8\times 10^4 & 1.08\times 10^8 \\ 1\times 10^6 & 78 & 1.67\times 10^{-7} & 6\times 10^5 & 3.6\times 10^{12} & 1.8\times 10^{10} & 1.08\times 10^{17} \\ 1\times 10^9 & 88 & 1.67\times 10^{-10} & 6\times 10^8 & 3.6\times 10^{18} & 1.8\times 10^{16} & 1.08\times 10^{26}\end{array}}\)

And the results are pretty interesting. We can determine what the trends are with the formulas above, and we can see how the various values scale with the frequency by replacing t in the equations with \(\frac{1}{6}\omega ^{-1}\). That gives us the following scaling arguments: \(v_m\sim \omega \), \(a\sim \omega^2 \), \(E\sim \omega^2 \), and \(P\sim \omega^3 \). In other words, if we double the frequency of the steps we will double the maximum velocity, but the acceleration and the energy will change by 4x, and the required power will change by 8x! This comes out to be a huge power requirement for the higher frequencies.

To get an idea of how huge the power requirements become, here are some power equivalents on the same order of magnitude:
To get \(\small{0.1 W}\), you would need the power consumption of about 10 DVD drive lasers.
To get \(\small{100 W}\), you would need the electrical output of a 1×1 m solar panel in full sunlight.
To get \(\small{1\times 10^{5} W}\), you would need the power output of a typical automobile.
To get \(\small{1\times 10^{8} W}\), you would need the power output of a Boeing 777.
To get \(\small{1\times 10^{17} W}\), you would need the total power received by the earth from the sun.
And to get \(\small{1\times 10^{26} W}\), you would need about 1/3 the total power output from the sun.
(All order of magnitude power estimates are from this Wikipedia page.)

How does this highest frequency look with our other limits on velocity and acceleration? We should be OK on velocity, since \(6\times 10^8 m/s\) is still only 1/5 the speed of light, slow enough that we can still ignore relativistic effects. As for the stress that the object undergoes due to acceleration, that’s fairly simple to calculate too. Stress is simply force over area, given in this simple formula:

\(\displaystyle{\sigma=\frac{F}{A}}\) .

Where F is the force and a is the cross-sectional area. We can get the force from Newton’s 2nd law: \(F=ma\). For the area we will need to assume a cross-sectional area of the disks themselves. Assuming the disks are about 3 cm in diameter, that gives about 7 \(cm^2\) in area. Calculating the stress that each disk receives we get the following:
\(\begin{array}{cc} \omega ,s^{-1} & \sigma , \text{Pa} \\ \hline 1 & 510 \\ 10 & 5.1\times 10^4 \\ 100 & 5.1\times 10^6 \\ 1000 & 5.1\times 10^8 \\ 1\times 10^6 & 5.1\times 10^{14} \\ 1\times 10^9 & 5.1\times 10^{20}\end{array}\)

Looking up the strength of various materials, the highest two were for high-impact steel and diamond, both being around 1 GPa \(\left(1\times 10^9\text{Pa}\right)\). So from the table, we could expect to move 1000 disks per second, but the disks would fail due to the acceleration if we tried to go much faster than that.

Assuming that we could make disks out of impossibilium that can take any amount of stress, then for The Flash to complete a Tower of Hanoi with 88 disks, he would need to move 1 billion disks per second at a speed of about 1/5 the speed of light for 10 trillion years, and he would require the constant power output of about 1/3 of the sun (or a series of equivalent-sized stars, since a single star won’t last that long).

That’s it for this post, in the next post I’ll try to include relativistic effects for even faster speeds.

This entry was posted in General, Science. Bookmark the permalink.

5 Responses to Tower of Hanoi

  1. Porter says:

    Well played, brother.

  2. Porter says:

    If it’s The Flash doing this, I think we need to consider yet another constraint.

    As fast as he is, he’s not terribly bright. If we assume that he solved the tower in the traditional way, by letting it drop instead of accelerating and decelerating it as it goes down, then he’d be limited to a mere 7 moves per second.

  3. Elwin says:

    Not to nitpick, but 6 x 10^8 meters per second is *not* one-fifth the speed of light, but rather twice the speed of light. As such, relativistic effects must be considered (usually the point at which they must be considered is 0.1c, so they would need to be considered anyhow).

  4. admin says:

    That’s not really nitpicking, that’s pointing out a gross error. I had thought that c was another order of magnitude larger for some reason. I guess that would just limit you to 10 millions disks/s or so.

    If you’re willing to work out the calculations for relativistic effects, I’ll be happy to post them. I just don’t have the time right now.

  5. Elwin says:

    Ways in which relativity can mess with the results:

    1) Time Dilation. The closer to c you get, the more your watch slows down. Talking about “how long” it takes to do something starts to depend upon your frame of reference. From a relatively non-inertial frame of reference, the existing limitations are still in place. From the interial reference, things are decidedly different. Your watch runs slower by a factor equal to the Lorentz factor; here are a few values.
    0.50c Lorentz factor: 1.15
    0.90c Lorentz factor: 2.3
    0.99c Lorentz factor: 7.1
    0.999c Lorentz factor: 22.4

    So if you were travelling at 0.99c, only 1.9 billion years would have passed since the creation of the universe. This doesn’t change the fact that you couldn’t have done the 100-disc stack by this time, but Flash may argue that he has another 11-12 billion years left to finish the job, since only 1.9 billion years have passed from his viewpoint. If he were travelling exactly at the speed of light, then no time at all would have passed for him between the Big Bang and now.

    Related to Time Dilation is Time Travel. Time Dilation is caused simply by travelling at a high velocity. However, part of general relativity includes that
    a) Being near a gravitational force affects your time, and
    b) Acceleration(and deceleration) forces are indistinguishable from gravitational forces.
    The end result is that not only is your high velocity changing relative time, but your constant acceleration and deceleration is also changing relative time. If we assume the two effects to be roughly identical in magnitude, then you can basically double the effects of time dilation and call it good. An odd thought, though: If Flash is moving just his arms, and the rest of his body is stationary, then the rest of his body will age over 10 times faster than his arms. (Naturally, such a thought completely ignores issues such as circulating blood, the amount of oxygen his arm cells would need to move that frequently, or the amount of lactic acid his muscles would build up from such exertion)

    2) Mass Increase. The closer your speed is to c, the greater your mass is. The factors are identical to Time Dilation; at 0.99c, a 100g disc would weigh over 7kg. This would tire out Flash’s arms at a much faster rate, but shouldn’t affect disc-disc interaction, since we’re already considering that we have to decelerate the disc before coming back to rest.

    3) Length Contraction. The faster you travel, the shorter distances are in the direction of travel. What this means, in short, is that as Flash ramps up his speed, the distances between towers will change. He will probably find it difficult to fit the discs into the pegs, unless he ramps up speed at a slow enough rate so that the distance changes slowly. This buildup time will naturally reduce the number of discs he can handle in the required timeframe(to do actual calculations on this, we would need to make several assumptions, such as determining how fast the distance can change without Flash missing a peg).

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.