Kyle Touhey - 54116025
kyle@touhey.net
MATH 308
Term Project, FALL 2002
The Sierpinski Gasket
Table of Contents:
Introduction
The Sierpinski Gasket is an interesting mathematical idea that gives visualization to many mathematical concepts. It is named for the Polish mathematician who first proposed the idea. The concept is a fractal that is an equilateral triangle which can in turn then be subdivided into four separate equilateral triangles, each of ¼ the initial size. These next triangles then can be subdivided again and the fractal proceeds in such a manner. But before we go into an elaborate discussion of the mathematical implications of the gasket, lets first look at an example of a problem that, at first, may seem totally unrelated:
The Towers of Hanoi Puzzle
There is some discrepancy as to when the puzzle was invented: mathematicians claim that it was the French mathematician Edouard Lucas who first proposed the problem in 1883. The more traditional idea was that an ancient monk thought of the dilemma of the end of the universe. In order to give it a timeframe, he came up with the problem. He spoke of three diamond poles, one of which had 64 golden disks stacked upon it. The disks are each slightly smaller than the others, with the largest one on the bottom. The universe was said to end when all of the disks were stacked in the same order on the third pole. It is the fulltime job of many monks to move the disks from pole to pole, with the condition that no disk sits on top on a disk smaller than itself.
I have illustrated an example of the problem, but for simplicity’s sake, I have only put on three disks.
Notice from the postscript file that 7 steps were required to move all of the disks to the final pole. Also notice that this was the quickest possible solution, but that there actually many other orders of disk movements possible in order to complete the puzzle.
As this point, it seems necessary to explain how I knew which movements to make in order to minimize the steps. We will see in the following sections, how the number of steps required for the 64 disks is related to the number of steps for the 3 disks. To do this, I introduce the idea of a Puzzle Graph…
Puzzle Graphs
Puzzle graphs are important in mathematics not only for solving game solutions, but for any situation where it is useful to find a multitude of solutions from a selection of options. By definition, a puzzle graph is:
1. For a given graph G, puz(G) is a graph whose nodes are all the labelings of G: V(puz(G)) = {f: f is a labeling of G}.
2. Two nodes of puz(G) are connected by an edge iff there is a legal move that transforms one labeling into the other.
-def from Cut-the-knot.com
This is to say that any vertex of the graph is a possible state of the puzzle at any one time, and that the edges connecting the vertices is/are the move(s) possible from the corresponding state in order to get to the current state.
So then for the first graph of the Towers of Hanoi puzzle for 1 disk, we can see that the puzzle graph is simply a triangle, each vertex of which has a label number 1..3. The fact that there are 3 vertices is due to the fact that there are three poles. Since there is only one disk, the label number is the pole on which the disk currently sits. To move the disk to any other pole, it just takes one move, thus only one edge.
We can see that the graph for the puzzle with two disks is significantly more complex. Each of the vertices now has a label with 2 numbers. These are now the poles on which the two separate disks sit. But a vertex is still a single state of the problem. So we can now also see that moving from one state to another takes more that just one (or possibly two = 1 per disk) move. Because of the rules of the puzzle, we cannot jump from the (1,1) state, with both disks on the first pole to (3,3), with both disks on the final pole. We must follow an appropriate path.
The puzzle graph for three disks is now MUCH more complex (take note of this, it become important later), but it still satisfies the rules of state, now with each vertex’s label having three numbers – the pole-state of each of the three disks. Now that we have a puzzle graph for our three disks problem, I can show you how the quickest possible solution was found. Since our initial state is (1,1,1) and our goal state is (3,3,3), we can see that the shortest path between the two is simply along the right side of the graph triangle. This equates to 7 sides, which is the number of moves required.
NOTE: this is not the only solution. Any connected path will work, however this is the shortest.
More Disks on the Towers of Hanoi
Now take a look at the quickest solution to the Towers of Hanoi puzzle with 4 disks. We can see that there are 15 steps. So the puzzle graph would therefore have 15 edges on each side. Notice that there are actually 15 +1 = 16 vertices in the path of those 15 steps.
But also notice this…
1 disks = 1 step = 2 vertices
2 disks = 3 steps = 4 vertices
3 disks = 7 steps = 8 vertices
4 disks = 15 steps = 16 vertices
We can assume that the pattern goes on like this because the every time we add a disk to the initial stack of N disk, we now have N + 1 disks. Think of the steps required to move N disks to pole three as a function f(N). Since to move a new disk (# N + 1) – assume it is on the bottom – we need to move all of the disks above it in the same fashion as f(N). Therefore f(N+1) = f(N) + g(1), where g is the steps to move the bottom disk. So now change the destination of f(N) to be pole2 (the middle pole). For f(N+1) we then need to move all the N disks f(N) : pole1 -> pole2, then move the bottom disk to pole 3 and then AGAIN move all N disks with f(N) : pole2 -> pole3 to make all of the N + 1 be finally on the stack of pole3. We can see that for each increasing N number of disks, the number of steps therefore takes exponential time (we can call the function Iterated or Recursive) and therefore f(N+1) = 2*f(N) +1 steps.
Building the Sierpinski Gasket
We need now to put our Towers of Hanoi example to the side in order to explain the basics of the primary topic – the Sierpinski Gasket.
We will get into its properties later but first we need to build one. The gasket is based on regularity and repetition within repetition. Since an actual Sierpinski Gasket is a triangle composed of triangles, composed of triangles, and so on, for an infinite amount time, I have broken down the construction of the gasket into steps that we shall call ‘degrees’ of the Sierpinski Gasket. The degree can be seen as the number of times that the triangle(s) are subdivided within themselves.
I have done two implementations of two different methods for constructing the gasket, as both types will be useful to us for different ideas. The first method simply draws a triangle and then draws triangles within it and so on, producing an image like:
The second implementation fills a triangle with an initial colour. Inverted subtriangles that are ¼ the size of this supertriangle are then placed in the centre to intersect vertices with the midpoints of the sides of the supertriangle. The algorithm then repeats itself of each of the 3 smaller subtriangles still not filled. It produces an image like:
Please also take note to look at the PS code for the implementation to notice the differences in the two methods, as well as the mathematical processes by which the triangles draw themselves (we will discuss more later). Notice that, when the same size and degree are chosen for each, that the images look almost identical (except for color – but that is aesthetic). The images are mathematically identical at infinity.
Sierpinski and the Towers
So now that we have our Sierpinski Gasket, what does it mean to the Towers of Hanoi problem? Well, actually the Towers of Hanoi problem can be explained in a way, using the gasket, but more importantly, the Towers puzzle serves as a tangible example for the abstract ideas that come out of the gasket. It is simple to see how they are related by looking at the graphs of each.
Just visually, one can see how similar the graphs look. And make a point of noticing the match of the # of degrees to the # of disks and how the paths seem to align themselves accordingly. The key concept to convey from both of these ideas is that of repetition and recursion towards the infinite. We can see how both use exponentials in their creation. In fact, more importantly is the idea that working backwards from this exponential idea, we can see that each part is a reiteration of itself. Which brings us to self-similarity…
Self-Similarity
An important idea that comes from the Sierpinski Gasket, is the mathematical idea of self-similarity. It is derived from the previously mentioned concept of repetition and recursion, as well as the idea of geometric balance (very useful for many proofs and the like). Since the gasket is triangular, we need to stack 3 subtriangles in order to achieve the same vertices. Because the gasket is an equilateral, we then know that all of the 3 subtriangles must be congruent. In fact, since they share an angle with the original triangle, and are equilateral (with sides = half the sides of the original), the subtriangles must be SIMILAR to the original.
This idea of triangular similarity is especially important in the case of the gasket because if we realize that each subtriangle of the gasket is, itself, actually another gasket with the same relative properties as the original gasket. This is to say that a Sierpinski Gasket is composed of other Sierpinski Gaskets of half the size. This idea is further recursed so that each of the sub-gaskets is in turn composed of gaskets and so on, towards infinite. Look how the number of paths in the initial implementation of the gasket increases exponentially to support this.
We saw the same sort of idea with the construction of the puzzle graph for the Towers of Hanoi with 1,2, and 3 disks; with each one being composed of the others. So then we can use the idea from the Sierpinski gasket to determine the number of moves for any number of disks. Look at the graph of 2disks compared with that of three 3disks. Now, remember that the #steps f(N+1) = 2* (#steps f(N)) + 1, this is because we want only the shortest path from one extreme vertex (1,1,1) to another (3,3,3), which is along the outer edge. So along the edge, the graph of N+1 is composed of 2*(graph of N) plus one more move (to move the very bottom disk to pole3). We can see the self-similarity at work here in the graph.
-But we still haven’t answered why the world would end when the puzzle was completed for 64 golden disks.
Infinity
The final important concept is that of infinity. Notice that when building the sierpinski gasket, the time that it takes your computer to draw the gasket significantly increases with the degree. this is because it is an exponentially increasing function. Every time a gasket is drawn of a certain degree, it must draw THREE gaskets of a degree only 1 smaller. Therefore, it will not take long for the number of operations performed to become VERY large, and tend towards the infinite.
Much like a limit towards infinite, we can see how the function performs. In the following diagram, make sure to follow the progress along the number line as a sierpinski gasket is formed by filling. If the gasket were ever formed at an infinite degree, the entire triangle would be filled in with red. Because of the limitations of the human eye and computer monitors, the triangle should ‘appear’ red at some point. All that point, we can call the number of fills to simply be VERY LARGE, as opposed to the infinite that we will never bother to reach. The number line is from 0 to 1 and it shows the blue dot as the relative size of the subtriangles that are being filled in red; and the red line shows the percentage of the triangle that is filled red (assuming 1 is full <- at infinite):
Notice that the triangle appeared entirely red around a degree of 10 or 11 (depending on your computer). This is a very small number relative to infinite (although, what isn’t), yet it produces relatively the same ‘effect’ as an infinite degree.
Now extend this idea to what is know about the Tower of Hanoi problem. We saw the similarity in the puzzle graph and the gasket (degree = #disks) in the comparison before. Since 64 disks is much larger than degree 10 in their terms, and 10 produces effects similar to those at infinite, we can then see how a Towers of Hanoi puzzle at 64, even if the disks were moved one step per second, would take infinite time. From there it is all philosophy as to why the world will end!
References