The Sierpinski Gasket and Pascal's Triangle ------------------------------------------- Ever seen a pegboard? The pegboard is a mechanical computer made of nails driven into a board, together with some small metal or plastic balls. The board is placed vertically, and nails protrude from it horizontally. When you drop a ball onto the side of a nail, it will (assuming it wasn't dropped from too high, so that it won't bounce back upwards) end up rolling either to the left of the nail or to the right. | | | | v . / \ / or \ v v If the nail is hammered in evenly and the ball is dropped directly on top of it, there should be a 50% chance that the ball will fall to the left, and a 50% chance that it will fall to the right. The more carefully the pegboard is made, the more likely it is that this is what will actually happen. On a completed pegboard, there are several tiers of nails, and each tier contains one more nail than the tier above it. They are arranged in a triangle, something like this: stream of balls o o o o o . . . . . . . . . . <------ a tier of nails (containing four nails) . . . . . <------ another tier (containing five nails) . . . . . . . . . . . . . | | | | | | | | | | | | |o|o| | | | | | |o|o|o|o| | | | | |o|o|o|o| | | <------- columns collecting balls | |o|o|o|o|o|o| | |o|o|o|o|o|o|o|o| |_|_|_|_|_|_|_|_| At the bottom of the pegboard, it's usual to have a number of columns to collect the balls. Each column is placed so that balls which ended up falling to the left from the peg immediately right of that column, or falling to the right from the peg immediately to the left of that column, will land inside the column. We would expect that more balls would tend to end up in the central columns than in the columns on the edges, because there are more ways for a ball to end up in the center than on the edges. In fact, what the pegboard computes is a graph of what's known in statistics as a normal curve or Gaussian distribution curve; it's also called a "bell curve" because it looks something like a bell. The greater the number of pegs in your pegboard, and the longer you send balls rolling through it, the more accurate a picture of the normal curve you'll end up with. This curve is the same curve you'd see if you graphed the frequency distribution of something like height or weight over a large randomly-selected population. In fact, statisticians and demographers and social scientists are constantly doing this; they always see the same curve. So do quality-control engineers in factories who sample products and measure their quality; so do natural scientists who measure the error or range of values observed in almost any experiment, if the experiment is repeated over and over again. The normal distribution is a deep law of nature which shows up in practically any situation where a large number of measurements are taken with some variation. Let's think about the number of paths a ball could take which would lead it to end up landing in a particular column. We can start out with zero tiers of pins and one column: |1| <----- the ball just falls directly into the column; there |_| are no pins for it to bounce off of How about one tier of pins and two columns? . |1|1| <--- there's one way to land in the left-hand column |_|_| and one way to land in the right-hand column If we added another tier, the situation would get more interesting: . . . |1|2|1| <--- there's one way to land in the column at either |_|_|_| end, and two ways to land in the middle How do we know this? Well, let's replace the pins themselves by digits showing the number of ways of reaching a given pin from above: 1 1 1 |1|2|1| <--- you can reach either end only from the pin right |_|_|_| above it, but you can reach the middle in two ways There's a general rule developing: the number of ways of reaching a pin is the sum of the number of ways of reaching the two pins right above it. (Pins on the ends only have a single pin "right above" them, and there will always be only one way of reaching a pin on the end.) Similarly, the number of ways of reaching a column is the sum of the number of ways of reaching the two pins right above that column. 1 1 1 1 2 1 <---- the number of ways of reaching the pins in this tier corresponds to the number of ways of reaching the corresponding columns in the diagram above |1|3|3|1| <---- and, again, the number of ways of ending up in a |_|_|_|_| given column is obtained by adding up the number of ways of reaching the pins directly above it This rule keeps showing us the number of ways through the pegboard as we add more tiers: 1 1 1 1 2 1 1 3 3 1 |1|4|6|4|1| |_|_|_|_|_| 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 |1|5|1|1|5|1| <---- now we have numbers with two digits, so let's |_|_|0|0|_|_| make this diagram a little wider 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 | 1 | 6 | 15| 20|15 | 6 | 1 | |___|___|___|___|___|___|___| What we're beginning to draw is the top of an infinitely large triangle, in which each tier is obtained from the tier immediately above it by adding up adjacent entries. Here are the first twelve tiers of that triangle: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1 1 11 55 165 330 462 462 330 165 55 11 1 1 12 66 220 495 792 924 792 495 220 66 12 1 This triangle is called Pascal's triangle, after Blaise Pascal (1623-1662). It has many wonderful properties. One of the applications is in algebra: (x+1)^0 = 1 (x+1)^1 = 1x + 1 (x+1)^2 = 1x^2 + 2x + 1 (x+1)^3 = 1x^3 + 3x^2 + 3x + 1 (x+1)^4 = 1x^4 + 4x^3 + 6x^2 + 4x + 1 (x+1)^5 = 1x^5 + 5x^4 + 10x^3 + 10x^2 + 5x + 1 The pattern continues: (x+1)^12 = 1x^12 + 12x^11 + 66x^10 + 220x^9 + 495x^8 + 792x^7 + 924x^6 + 792^5 + 495x^4 + 220x^3 + 66x^2 + 12x + 1 The coefficients of the terms in (x+1)^n are the same as the numbers on the nth row of Pascal's triangle, if we say that the top row is row 0. (This is a simple way of stating a rule called the Binomial Theorem.) I'm going to stop talking about properties of Pascal's triangle for a little while, and talk about a geometric figure called the Sierpinski gasket. Drawing pictures of the Sierpinski gasket is the goal of this assignment. Draw an equilateral triangle, point upwards, and call it A. Now find the midpoint of each segment in the triangle; by connecting these midpoints, you can produce a new equilateral triangle, upside down, which we'll call A'. Now black out A' (shade it black). You should now see four smaller equilateral triangles -- three white and one black. The white triangles are all facing upwards; the black triangle, A', is facing downwards. Each of these smaller triangles is 1/4 the area of the original triangle A. We'll call the new white triangles B1, B2, and B3. So A', B1, B2, and B3 together make up A. Now, for each triangle B1, B2, and B3, find the midpoint of each segment, and connect those midpoints to make a new, smaller triangle -- which you'll shade black. These smaller shaded triangles will be called B1', B2', and B3'. Within each of the triangles B1, B2, and B3, you'll now see three new (smaller) white triangles. If you repeat this process once more, drawing a smaller inverted black triangle upside-down inside each remaining white triangle, you'll have a pretty good picture of what's coming. The resulting figure seems to contain a copy of itself -- each upright white triangle appears to contain the entire original white triangle, in miniature. If you'll kindly now repeat the process an infinite number of times, you'll be done, and you'll obtain a fractal. This fractal is called the Sierpinski gasket, after Waclaw Sierpinski (1882-1969). It's a prettier two-dimensional version of a somewhat more boring one-dimensional fractal called the Cantor dust. Without describing anything about the geometry of the Sierpinski gasket, we can produce a high-resolution picture of it using Pascal's triangle! This is because the oddness or evenness of each number in Pascal's triangle (called that number's parity) forms a picture of the Sierpinski gasket within that triangle. If you take Pascal's triangle out infinitely far, you will get an infinitely accurate picture of the gasket. If you stop at some point, your picture of the gasket will stop too (but it may still be very respectable, and suitable for framing). To produce the Sierpinski gasket picture, you just have to calculate and print the successive rows of Pascal's triangle. But instead of printing numbers in each position, you should print one symbol if the number in that position is odd, and a different symbol if it's even. I recommend printing "o" for an odd number and " " for an even number. You'll also have to tackle the problem of how to center your output on the screen. There is a standard technique for centering an arbitrary string, and you may want to discover that technique. | For | | example, | | this | | text | | is | | centered | | left | | to | | right | | between | | these | | two | | vertical | | lines. | A centering rule would tell you how many spaces you need to print to the left of your text in order to make it appear centered on the screen. If you like, instead of actually calculating the numbers in Pascal's triangle, you can just calculate whether they would be odd or even, since that's all we care about for purposes of displaying the Sierpinski gasket. You can do this by keeping in mind that odd + odd = even even + even = even odd + even = odd even + odd = odd or, if you represent "odd" by 1 and "even" by 0, 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 0 This rule is sufficient to produce your Sierpinski gasket. Katie tells us that a pegboard is on display at the Exploratorium right now (March 2002). You can also seen one at the Boston Museum of Science.