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.
