Wednesday, February 8, 2012

Pascal Triangle

Often, my explanations of things tend to get round-about, primarily because I need to explain 2 or 3 unrelated items before getting to my main point. 3 guesses as to what's going to happen next...

First, one of the comics I like reading is Richard Thompson's Cul de Sac. This comic isn't drawn all that well, but the character interactions are fairly bizarre at times, which makes it fun. Lately, some of the strips have been repeats with the art recolored. Richard had left a comment on GoComics to the effect that the better version of one particular strip was on his blog. Now, his blog talks about some of the personal problems he has, one of which is that he suffers from Parkinson's Disease. In one entry, he mentioned that he's going to start physical therapy, which consists of practicing more exaggerated moves, and he accompanied the article with a picture of John Cleese doing the Monty Python "Department of Silly Walks" sketch.

(Department of Silly Walks T-Shirt.)

Now, this poster reminded me of Pascal's Triangle, which I learned about in math class in high school, but hadn't played with recently. The basic idea here is that you offset each row by half a square, so that each square is directly under the 2 squares above it. The value of each square is then the sum of the two squares of the previous row. Of course, the explanation is usually given the other way around, starting with "1" in the top square, and then adding the contents of two adjacent squares to get the value of the square on the subsequent row. Along the edges of the pyramid, you just treat it as "0 + 1" all along the line. It's insanely easy to write up an Excel spreadsheet for this, but the numbers get too large to display in the cells properly after 10 rows or so.

(Animated gif showing how to calculate the pyramid, from the wiki entry.)

What I hadn't known before is that there's a trick where you color the squares based on whether the numbers are even or odd (or divisible by 3, 4, 5 etc. The interesting pattern is base-2.) The result is actually a fascinating little guy that I first encountered when I learned about fractals - the Sierpinski triangle. So, naturally I had to hand-draw it. Actually, it's a very easy process and doesn't require any adding, making it a simple matter of cut and paste. For any cell that you're working on, look at the two cells directly above it. If only one cell is black, color the current one black. Otherwise, if both of the above cells are white or both black, then leave the current cell white. It's an exclusive-OR operation (which I was really hoping I had invented, but hadn't). When you get one triangle, just copy-paste it into the positions of the next two lower triangles. A no-brainer. If you copy-paste enough, you can make a Sierpinski triangle that's visible from space.

(Hand-drawn Sierpinski triangle made by following the XOR principle. About 3' x 3'.)

I was trying to figure out the best way to make the grid, initially considering hand-drawing it on a sheet of construction paper. But, I stopped by the 100 yen shop on my way home, and found a notebook of graph paper that turned out to be perfect for this project ($1.40 for 50 pages). I picked up a black magic marker at the same time. I tested out the marker on the paper first, and as suspected, it bled through the surrounding paper. Then I confirmed that pre-drawing the grid outline in pen caused the bleeding to stop (or, at least, to be better confined to within the square). So I then spent a couple of hours drawing in the grid lines for the pyramid, and another couple drawing in the actual pyramid following my XOR procedure. The final assembly is 75 rows, and 75 squares wide at the bottom, or about 3' x 3'.

There's an amusing property to each larger triangle. Looking at the above picture, the very top white dot is just 1 square. The next larger white triangle down is 3 squares tall. This is followed by one 7 squares tall, and the next is 15 squares, finally the last one is 31. The question becomes "what's the size of the next larger white triangle being constructed"? Well, 3-1=2. 7-3=4. 15-7=8. 31 -15=16. Presumably if you're adding twice as many rows each time, then 2x16=32, and 31+32=63 (Another way to figure is is 2^n - 1). And, yes, the next triangle in process is in fact 63 squares tall (2^6 - 1). Actually, it should be pretty obvious that what you're doing is rubber-stamping one triangle assembly 4 times to make the next larger one, but leaving out the rubber-stamp in the middle, which doubles the height of each larger assembly. In fact, the Sierpinski triangle is made by taking an equilateral triangle and removing the central 25%, and then repeating the process for all subsequent smaller solids that result, eventually making a sponge that converges on 100% air after 25-30 iterations. You can get the same effect by using a square - it's called the Sierpinski Carpet.

(Printer-ready version, A4 size.)

Because it is such a predicable process, I decided next that I might as well draw up a basic triangle in Gimp. This took another 2 hours, in part because Gimp isn't very good at snap-to-grid when you do a lot of copy-pasting. I was forced to retry the picture several times before I got what I was looking for. This one is the size of an A4 sheet of paper. Just make 100 copies, cut it out along the lines and tape it together to get that "visible from miles away" effect.

Not quite the same as having a 24' x 24' John Cleese poster that you can give to Alice to play with, but close enough.

No comments: