# Chaos in the Classroom

Robert L. Devaney
Department of Mathematics
Boston University
Boston, MA 02215

One of the most interesting applications of technology in the mathematics classroom is the fact that it allows teachers to bring many new and exciting topics into the curriculum. In particular, technology lets teachers bring some topics of contemporary interest in research mathematics into both middle school and high school classrooms.

The mathematical topics of chaos and fractals are particularly appropriate in this regard. They are timely---many ideas in these fields were first conceived during the students' lifetimes. They are applicable---fields as diverse as medicine, business, geology, art, and music have adopted ideas from these areas. And they are beautiful---there is something in the gorgeous computer generated images of objects such as the Mandelbrot set, Julia sets, the Koch snowflake, and others that capture students' interest and enthusiasm.

Therein, however, lies the problem. Many research mathematicians cringe at the sight of ``still another fractal.'' Most often, discussions of chaos and fractals degenerate to simple ``pretty picture shows,'' devoid of any mathematical content. As a consequence, students get the idea that modern mathematics is akin to a video game---lots of computer-generated action, but mindless activity at best.

This attitude is both unfortunate and unnecessary. There is mathematics behind the pretty pictures, and moreover, much of it is quite accessible to secondary school students. Furthermore, the mathematics behind the images is often even prettier than the pictures themselves! In this sense it is a tragedy that students come so close to seeing some exciting, contemporary topics in mathematics, yet miss out in the end. Our goal in this note is to help remedy this situation by describing some easy-to-teach topics involving ideas from fractal geometry.

# The Chaos Game

One of the most interesting fractals arises from what Michael Barnsley has dubbed ``The Chaos Game'' [Barnsley]. The chaos game is played as follows. First pick three points at the vertices of a triangle (any triangle works---right, equilateral, isosceles, whatever). Color one of the vertices red, the second blue, and the third green.

Next, take a die and color two of the faces red, two blue, and two green. Now start with any point in the triangle. This point is the seed for the game. (Actually, the seed can be anywhere in the plane, even miles away from the triangle.) Then roll the die. Depending on what color comes up, move the seed half the distance to the appropriately colored vertex. That is, if red comes up, move the point half the distance to the red vertex. Now erase the original point and begin again, using the result of the previous roll as the seed for the next. That is, roll the die again and move the new point half the distance to the appropriately colored vertex, and then erase the starting point. See Figure 1. Figure 1: Playing the chaos game with rolls of red, green, blue, blue.

Now continue in this fashion for a small number of rolls of the die. Five rolls are sufficient if you are playing the game ``by hand'' or on a graphing calculator, and eight are sufficient if you are playing on a high-resolution computer screen. (If you start with a point outside the triangle, you will need more of these initial rolls.)

After a few initial rolls of the die, begin to record the track of these traveling points after each roll of the die. The goal of the chaos game is to roll the die many hundreds of times and predict what the resulting pattern of points will be. Most students who are unfamiliar with the game guess that the resulting image will be a random smear of points. Others predict that the points will eventually fill the entire triangle. Both guesses are quite natural, given the random nature of the chaos game. But both guesses are completely wrong. The resulting image is anything but a random smear; with probability one, the points form what mathematicians call the Sierpinski triangle and denote by S (see Figure 2). Figure 2: The Sierpinski triangle

A few words about the coloring here is in order. We have used color merely to indicate the proximity of the vertex with the given color. For example, the portion of the triangle closest to the green vertex is colored green, and so forth.

There is some terminology associated with the chaos game that is important. The sequence of points generated by the chaos game is called the orbit of the seed. The process of repeating the rolls of the die and tracing the resulting orbit is called iteration. Iteration is important in many areas of mathematics. In fact, the branch of mathematics known as discrete dynamical systems theory is the study of such iterative processes.

There are two remarkable facets of the chaos game. The first is the geometric intricacy of the resulting figure. The Sierpinski triangle is one of the most basic types of geometric images known as fractals. The second is the fact that this figure results no matter what seed is used to begin the game: With probability one, the orbit of any seed eventually fills out S. The words ``with probability one'' are important here. Obviously, if we always roll ``red,'' the orbit will simply tend directly to the red vertex. Of course, we do not expect a fair die to yield the same two numbers at each roll.

# The Sierpinski triangle.

The Sierpinski triangle S may also be constructed using a deterministic rather than a random algorithm. To see this, we begin with any triangle. Then we use the midpoints of each side as the vertices of a new triangle, which we then remove from the original. This leaves us with three triangles, each of which has dimensions exactly one-half the dimensions of the original triangle, and area exactly one-fourth of the original area. Also, each remaining triangle is similar to the original.

Now we continue (or iterate) this process. From each remaining triangle we remove the "middle" leaving behind three smaller triangles each of which has dimensions one-half of those of the parent triangle (and one-fourth of the original triangle). Clearly, 9 triangles remain at this stage. At the next iteration, 27 small triangles, then 81, and, at the Nth stage, 3^N small triangles remain. It is easy to check that the dimensions of the triangles that remain after the Nth iteration are exactly 1/2^N of the original dimensions. See Figure 3. Figure: Deterministic construction of S

# Why does the Sierpinski triangle arise from the chaos game?

Students are always intrigued when they first see the Sierpinski triangle emerge from the random chaos game, but there is a simple explanation of why this happens. Suppose we start with a point somewhere in the middle of the largest white (removed) triangle in the Sierpinski triangle.

Where does this point move after one roll of the die? As in Figure 4, we see that this point hops into one of the three next-smaller triangles, since these triangles represent all points that are half the distance to the three vertices from points in the largest removed triangle. After one more iteration, this point then moves to the next smallersize triangle. And so forth. Figure: After one iteration of the chaos game

Now continue. At the next iteration, the point hops into one of the 9 next small triangles, then into the next smaller triangles, and so on. Eventually (after very few iterations), the point enters a small triangle that is for all intents and purposes invisible.

In actuality, the orbit of a point that starts in any of the removed triangles will never ``reach'' the Sierpinski triangle. Rather, it will continue to lie in successively smaller removed triangles. Of course, these removed triangles very quickly become microscopic in size, so for all practical purposes the orbit looks like it lies on S. Mathematicians says that the orbit of the seed is attracted to S. Sometimes S is called a strange attractor.

# Playing the chaos game in class

There is a wonderful idea due to a number of individuals [Peitgen, et. al] provides an easy way to play the chaos game without using technology. Give each student (or group of students) an overhead transparency onto which you have copied the vertices of the original triangle (so they all are playing the same chaos game). Have the students choose the colors of the vertices and the original seed. Instead of using a marking pen to indicate the seed, have the students use the small circles that form the output of a three-hole punch. This allows them to perform the first few iterations by simply moving the ``dot'' rather than erasing.

Now have one student roll a die and another take charge of moving the ``point'' half the distance to the indicated vertex. A wonderful idea for moving the point exactly half the distance is the ``half-way ruler'' invented by Henri Lion. See Figure 5. Figure 5: The half-way ruler

After seven or eight iterations with the movable point, have the students begin to track the orbit by recording the points on the orbit using a marking pen. Depending upon the class-size, 10 iterations of the chaos game by each group should be sufficient. Gather all of the transparencies and align them correctly on the overhead. Provided nobody has goofed, you will see the beginning of a good representation of the Sierpinski triangle. (It is important to use transparencies that are ``see-through''; some transparencies become opaque when several are piled together.)

Another interesting and valuable classroom activity involves target-shooting. Draw one of the images in the deterministic construction of S on the board or the overhead projector. Actually, it is best to begin at a relatively low level, say the second or third stage (so either 9 or 27 triangles remain). Fix a seed, perhaps one of the 3 vertices. Then color one of the triangles that remain at the lowest stage of the construction (the smallest triangles that have not yet been thrown out or subdivided). This triangle is the target. Then the game is to move the seed into the interior of the target in the smallest number of moves. This is not a random game any longer: the students have to determine which rolls of the die put the seed in the target in the smallest number of rolls. See Figure 6. Figure 6: A target for the chaos game

There is no unique most efficient method to hit the target, as there are several alternatives. However, there is a least possible number of moves that cannot be beaten. At first, students seem to have a great deal of fun challenging one another with this game. Later they turn their attention to finding the algorithm that yields the most efficient solution. It is a wonderful exercise for students to try to find this winning strategy, and an even more beneficial exercise for them to explain their strategy once they have found it.

As part of the Dynamical Systems and Technology project at Boston University, there is a Java Applet available that students can use to play this game interactively. The URL is {\tt http://math.bu.edu/DYSYS/applets/ }.

# Self-similarity

One of the basic properties of fractal images is the notion of self-similarity. This idea is easy to explain using the Sierpinski triangle. Note that S may be decomposed into 3 congruent figures, each of which is exactly 1/2 the size of S! See Figure 7. That is to say, if we magnify any of the 3 pieces of S shown in Figure 7 by a factor of 2, we obtain an exact replica of S. That is, S consists of 3 self-similar copies of itself, each with magnification factor 2. Figure 7: Magnifying the Sierpinski triangle

We can look deeper into S and see further copies of S. For the Sierpinski triangle also consists of 9 self-similar copies of itself, each with magnification factor 4. Or we can chop S into 27 self-similar pieces, each with magnification factor 8. In general, we may divide S into 3^n self-similar pieces, each of which is congruent, and each of which may be maginified by a factor of 2^n to yield the entire figure. This type of self-similarity at all scales is a hallmark of the images known as fractals.

# Fractal Dimension

Students (and teachers) are often fascinated by the fact that certain geometric images have fractional dimension. The Sierpinski triangle provides an easy way to explain why this must be so.

To explain the concept of fractal dimension, it is necessary to understand what we mean by dimension in the first place. Obviously, a line has dimension 1, a plane dimension 2, and a cube dimension 3. But why is this? It is interesting to see students struggle to enunciate why these facts are true. And then: What is the dimension of the Sierpinski triangle?

They often say that a line has dimension 1 because there is only 1 way to move on a line. Similarly, the plane has dimension 2 because there are 2 directions in which to move. Of course, there really are 2 directions in a line -- backward and forward -- and infinitely many in the plane. What the students really are trying to say is there are 2 linearly independent directions in the plane. Of course, they are right. But the notion of linear independence is quite sophisticated and difficult to articulate. Students often say that the plane is two-dimensional because it has ``two dimensions,'' meaning length and width. Similarly, a cube is three-dimensional because it has ``three dimensions,'' length, width, and height. Again, this is a valid notion, though not expressed in particularly rigorous mathematical language.

Another pitfall occurs when trying to determine the dimension of a curve in the plane or in three-dimensional space. An interesting debate occurs when a teacher suggests that these curves are actually one-dimensional. But they have 2 or 3 dimensions, the students object.

So why is a line one-dimensional and the plane two-dimensional? Note that both of these objects are self-similar. We may break a line segment into 4 self-similar intervals, each with the same length, and ecah of which can be magnified by a factor of 4 to yield the original segment. We can also break a line segment into 7 self-similar pieces, each with magnification factor 7, or 20 self-similar pieces with magnification factor 20. In general, we can break a line segment into N self-similar pieces, each with magnification factor N.

A square is different. We can decompose a square into 4 self-similar sub-squares, and the magnification factor here is 2. Alternatively, we can break the square into 9 self-similar pieces with magnification factor 3, or 25 self-similar pieces with magnification factor 5. Clearly, the square may be broken into N^2 self-similar copies of itself, each of which must be magnified by a factor of N to yield the original figure. See Figure 8. Finally, we can decompose a cube into N^3 self-similar pieces, each of which has magnification factor N. Figure 8: A square may be broken into N^2 self-similar pieces, each with magnification factor N

Now we see an alternative way to specify the dimension of a self-similar object: The dimension is simply the exponent of the number of self-similar pieces with magnification factor N into which the figure may be broken.

So what is the dimension of the Sierpinski triangle? How do we find the exponent in this case? For this, we need logarithms. Note that, for the square, we have N^2 self-similar pieces, each with magnification factor N. So we can write Similarly, the dimension of a cube is Thus, we take as the definition of the fractal dimension of a self-similar object Now we can compute the dimension of S. For the Sierpinski triangle consists of 3 self-similar pieces, each with magnification factor 2. So the fractal dimension is  so the dimension of S is somewhere between 1 and 2, just as our ``eye'' is telling us.

But wait a moment, S also consists of 9 self-similar pieces with magnification factor 4. No problem -- we have as before. Similarly, S breaks into 3^N self-similar pieces with magnification factors 2^N, so we again have Fractal dimension is a measure of how "complicated" a self-similar figure is. In a rough sense, it measures "how many points" lie in a given set. A plane is "larger" than a line, while S sits somewhere in between these two sets.

On the other hand, all three of these sets have the same number of points in the sense that each set is uncountable. Somehow, though, fractal dimension captures the notion of "how large a set is" quite nicely, as we will see below.

# Changing the rules in the chaos game

The chaos game provides a wonderful opportunity for students to develop their geometric insight as well as their understanding of the geometry of linear transformations. As we have seen, if we choose 3 points on the vertices of an equilateral triangle and play the chaos game, moving half the distance toward the appropriate vertex at each stage, then the Sierpinski triangle S results. Note that these numbers are reflected in the geometry of S, for this figure consists of 3 self-similar copies of S, each 1/2 the size of the S (or, as we said earlier, with magnification factor 2).

We really should have called S the Sierpinski equilateral triangle, since there are other Sierpinski triangles. For, as shown in Figure 9, if we begin with vertices on a right triangle or on a triangle with an obtuse angle, different fractals result. However, each of these images consists of 3 self-similar copies, each with magnification factor 2.  Figure 9: Other Sierpinski triangles

Now let's vary the rules of the chaos game. Suppose we again start with 3 points at the vertices of an equilateral triangle. We will again move toward these vertices depending upon the roll of a die. This time, if the lower 2 vertices are chosen, we again move 1/2 the distance toward them. But if the top vertex is chosen, we move 2/3 of the way toward that vertex. A better way to say this (for reasons that will be clear in a moment) is: We compress the distance from the point to the top vertex by 1/3. Equivalently, we move our point on a straight line to the top vertex so that the new distance is 1/3 of the old. If we play the chaos game with these rules, a very different image results (figure 10A). However, note that this image consists of three self-similar pieces, two of which are exactly 1/2 the size of the entire image, while the other is 1/3 the size. Again, the number of basic copies is equal to the number of vertices we started with, and the magnification factors at each vertex correspond as well.  Figure 10: The result of playing the chaos game with 3 vertices and magnification factors 2, 2, and 3, and then with magnification factors 2, 3, 4

If we further refine the rules of the chaos game, we see that we can still read off the original rules we used to play the game from the geometry of the resulting figure. For example, in figure 10B, we used 3 vertices and magnificat ion factors 2, 3 and 4 to create the image (that is, we moved 1/2 the distance toward one vertex, 1/3 the distance toward another, and 1/4 the distance to the final vertex).

We may also vary the number of vertices used. For example, to produce figure 11A, we chose 6 points on the vertices of a regular hexagon and moved 1/3 the distance toward the appropriate vertex at each roll of the die. Note that this is a ``natural'' chaos game in the sense that we can number the vertices 1-6 and use the number that comes up at each roll to determine the vertex to move toward. We call this image the Sierpinski hexagon; note that it consists of 6 self-similar pieces, each with magnification factor 3. So the fractal dimension of this image is N^2.

Figure 11: The Sierpinski hexagon and pentagon

There is another famous fractal buried inside the Sierpinski hexagon. Note that the inner boundary of this figure is the well known Koch snowflake curve (see Devaney, 1990).

If we choose 5 vertices on a regular pentagon, and compress toward the vertices by a factor of 3/8 at each roll of a 5-sided die, the image in figure 11B results---a Sierpinski pentagon. Again we find 5 self-similar copies, each 1/3 the size of the original.

At this point it is interesting to guess what figure results when we play the chaos game with points on the vertices of a square and a magnification factor of 2. Most people expect a ``Sierpinski square.'' Wrong! The points fill out the entire square when the chaos game is played with these rules. But that is no surprise: After all, a square is a self-similar image that may be broken into 4 self-similar pieces, each with magnification factor 2. So we can again read off the rules of the chaos game from the resulting figure.

# Rotations and Animations

Another, more complicated type of chaos game results when we allow rotations as well as contractions toward specific vertices. For example, suppose we start with the vertices of an equilateral triangle. Again, when either of the lower two vertices are selected, we simply move half the distance toward them. But when the upper vertex is chosen, we first move 1/2 way toward the vertex, then we rotate the point about this vertex by 90 degrees in the counterclockwise direction. Note that we could equally well rotate first, then move 1/2 the distance toward that vertex. If we now play the chaos game with these rules, the image in figure 12 results. Note that this figure consists of 3 self-similar pieces, and each is 1/2 the size of the original, but the topmost piece is rotated by 90 degrees in the counterclockwise direction. Again, it is not so easy to predict what figure will result from playing the chaos game, but once we see it, there is no question what game we played to generate it.  Figure 12: The chaos game with 3 vertices, magnification factor 2, and one 90 degree rotation about the top vertex Figure 13: The chaos game with 3 vertices, magnification factor 2, and one 180 degree rotation about the top vertex

Rotations complicate the task of determining the chaos game that intuition to figure out some of these games. For example, how did we generate the fractals in figure 14?  One rather fun exercise for students who have access to good computing equipment to perform is to make a fractal "movie. This can be done by computing the images of a number of fractals generated by chaos games where each "frame" of the film is generated by changing the parameters (rotations or magnification factors) in the previous frame only slightly. In15A-C we show a "clip" of such a film. How did we generate this movie? Click on this icon to download the animation).
Figure 15A: How was this movie generated? You need to have a QuickTime Movie player in order to view the animation. Choose Loop in order to see the film continually. Click on this icon to download the animation). Click on this icon to download the animation).
Figure 15C (Dancing Triangles): And how was this movie generated? Warning: there is approximately 700K of data to download to view this film. For the answer, click HERE

# Summary

We have found that activities such as those discussed above serve to excite and to challenge students. Many of the chaos games were played in ``chaos clubs'' organized by Jonathan Choate, Beverly Mawn, and Mary Corkery in Boston public schools as after-school enrichment activities for students. While we compiled no concrete data, we have a lot of anecdotal evidence that students greatly enjoyed this kind of mathematics.

The mathematics involved in constructing and understanding chaos games runs the gamut from elementary algebra to linear algebra, from Euclidean to fractal geometry. Algorithmic thinking is a prerequisite for writing the simple graphing calculator program necessary to play the game with technology. Geometric transformations are at the root of the game. And probability and randomness lurk in the background. In short, chaos games provide the student with a wealth of different mathematical ideas and, at the same time, a glimpse at contemporary mathematics.

Note: This paper will appear in printed form in "New Directions for Teaching and Learning Geometry," ed. R. Lehrer, Erlbaum Associates. It appeared in abbreviated form in FOCUS, Volume 15, No. 3, June 1995, published by the Mathematical Association of America.

For this fractal, we used four vertices each with magnification factor 3. Two of the vertices featured no rotations, while the other two had rotations of 60 degrees and -60 degrees respectively. See below.

Incidentally, this fractal is the famous Koch curve. Vissza