Here’s a simple origami experiment to try. Start with a long strip of paper with different colors on the two sides—e.g., Orange (O) on one side, Indigo (I) on the other. Now fold the strip in quarters to form a flat “S-shape” as illustrated here (creases are drawn slightly rounded for ease of viewing):
As you look through the four layers from top to bottom, write down the colors you encounter, in order: the first layer shows Indigo (I), the second layer has Orange (O), and so on. The full order is IOOI, which looks suspiciously like the start of the Thue-Morse sequence. (This sequence was introduced last week.)
To continue the experiment, treat this figure as a single strip and fold the same flat S-shape again. There will be 16 layers down the middle:
Sure enough, the order of colors encountered is IOOI OIIO OIIO IOOI, which is the first 16 digits of the Thue-Morse sequence. This pattern will continue forever (or at least until the paper gets too thick to fold): every time you fold another S-shape, you quadruple the number of digits of the Thue-Morse sequence (can you see why?). Try to fold a third iteration! It looks like this (click for larger image):
But wait, there’s more! Now that we have these creased strips, what happens when we unfold them? Specifically, follow the existing creases and lay out the strips so that each crease makes a 90-degree angle. What shapes do we get? Surprisingly, they exactly fill triangular grids of squares:
Here’s a simple rule to generate a pretty sequence of 1s and 0s: Start with the list 1 (just one digit) and repeatedly form a new list by flipping all the bits (1s become 0s and vice versa) and attaching this to the end: $$1 \to 10 \to 1001 \to 10010110 \to 1001011001101001 \to \cdots.$$ For example, to get from 1001 to the next sequence, we swap 1s and 0s to form 0110, and then we join these together to make 10010110. By continuing this process we can make our list longer and longer, and the limiting sequence $$1001011001101001011010011001011001101\cdots$$ is called the Thue-Morse Sequence.
What did I mean by calling this sequence “pretty”? Well, what does this sequence “look like”? One way to visualize it is with a turtle program. Imagine a turtle (let’s call him Leo) walking along the plane, and treat the digits of the Thue-Morse sequence as a list of instructions for the turtle as follows: When Leo sees the digit 1, he steps forward one foot; a 0 tells Leo to turn left by 60 degrees. What does Leo’s path look like? Here are the first 32 instructions he follows:
The turtle follows these instructions on the first 32 entries of the Thue-Morse sequence: {1: Step; 0: Turn 60}.
And here are snapshots of his path as he gets farther into the Thue-Morse sequence:
Snapshots of the turtle's trajectories after 2^8, 2^10, 2^12, and 2^14 instructions, respectively.
Why did we pick these instructions? What if Leo turns 120 degrees instead of 60 degrees when he sees a 0?
The turtle follows the Thue-Morse sequence with a slightly different set of instructions: {1: Step; 0: Turn 120}. Shown here after 2^6, 2^8, 2^10, and 2^12 instructions, respectively.
If you zoom out and/or squint a little, these paths are roughly following a famous fractal called the Koch curve. And indeed, the more steps you draw, the closer the resemblance will become (as analyzed in these two papers: [MH2005] and [KZH2008]). But why stop here? What happens if we change the turtle’s instructions even more? I played around with some new rule sets, and these too show how the Koch curve seems innately “programmed” into the structure of the Thue-Morse sequence:
Three more pretty examples of the Thue-Morse sequence's "turtle power." In all three cases, the trajectories converge to the Koch curve. Left: {1: (Turn 180, Step); 0: (Turn 60, Step)}, after 2^8 instructions. Middle: {1: (Turn 180, Step); 0: (Turn 120, Step)}, after 2^10 instructions. Right: {1: Turn 180; 0: (Turn 15, Step)}, after 2^10 instructions.
Here’s a final challenge: if the Koch curve and the Thue-Morse sequence are so intimately related, shouldn’t we be able to find some turtle program instructions that trace the Koch curve without “squinting”? Specifically, the Koch curve is usually constructed as the limit of the following sequence of paths, where each iteration is made by stitching together four copies of the previous curve:
The Koch curve is constructed as the limit of these paths, where each curve is formed from four (shrunken) copies of the previous curve.
Is there a set of turtle instructions whose path traces exactly these curves? In fact, there is! These instructions work: {1: (Step, Turn 60); 0: Turn 180}.
Enough geometry already! Let’s switch gears and explore an interesting phenomenon in balanced grid coloring:
Problem: The numbers 1,2,…,100 are written in order in a \(10\times 10\) grid. Some grid cells are colored red, and the rest blue, in such a way that exactly half the cells in each row and each column are red (call this a balanced coloring). Show that the sum of the numbers in red cells equals the sum of the numbers in blue cells.
Examples of balanced grids: each grid has five red and five blue cells in each row and column. By the problem above, the red numbers and blue numbers add to the same total in each grid.
How can we understand this question? Notice that each row needs five red and five blue cells, but the values in each row do not need to balance. Indeed, the first row of the first example above is very skewed toward blue: \(\text{red}=1+2+3+4+5=15\) and \(\text{blue}=6+7+8+9+10=40\). In fact, every row in that example is very skewed to one side or the other! But the fact that every column also needs five red and five blue numbers somehow forces these skewed row sums to cancel each other out. This is essentially what the problem asks us to prove.
A (Not So Great) Start
Here’s one idea: let’s just test all the balanced grid colorings! There can’t be too many, right? Let’s start small. How many balanced \(2\times 2\) grid colorings are there? (Each row needs 1 red and 1 blue.) Just two: the first cell is either red or blue, and everything else is determined from there (cf. binary sudoku). And each of these has a red sum and a blue sum of 5, so we’ve verified the problem for \(2\times 2\) grids. What about \(4\times 4\)? With a little work, you can compute by hand that there are 90 balanced colorings of a \(4\times 4\) grid (try this!). That’s already a lot of cases to check. For \(10\times 10\) grids, it turns out that there are 6736218287430460752 balanced colorings! Maybe it’s time to look for a different method.
A Solution
Here’s a method that does work. Start with a zero in each grid cell; the red and blue sums are certainly equal (they’re both zero). Now we’ll modify the values one row or column at a time. If we add 1 to each cell in a column, then the red and blue sums each increase by 5 (because each column is balanced), so the sums remain equal. Do this once in the first column, twice in the second column, and so on, resulting in the middle grid below (which must therefore have equal red and blue sums):
Adding the same number to each cell in a row or column of a balanced grid keeps the red and blue sums equal. Applying this process to an initially all-zero grid yields the desired grid of 1,2,...,100 and solves the problem.
Now modify the rows: add 10 to the second row, 20 to the third row, etc., finally ending up with the numbers 1,2,…,100 in order. Each step preserves the fact that the red and blue sums match, so we’re done! Notice that this argument works for any even grid size; 10 is not special here.
About This Problem
This problem appeared (with different phrasing) in the 2001 Putnam Competition, a very challenging mathematics competition for undergraduate students in the United States and Canada. This competition’s directories contain even more solutions and insights into this problem (Problem 2001 B1).
To round off our series on round objects (see the first and second posts), let’s compute the sphere’s surface area. We can compute this in the same way we related the area and circumference of a circle two weeks ago. Approximate the surface of the sphere with lots of small triangles, and connect these to the center of the sphere to create lots of triangular pyramids. Each pyramid has volume \(\frac{1}{3}(\text{area of base})(\text{height})\), where the heights are all nearly \(r\) and the base areas add to approximately the surface area. By using more and smaller triangles these approximations get better and better, so the volume of the sphere is $$\frac{4}{3}\pi r^3 = \frac{1}{3}(\text{surface area})\cdot r,$$ meaning the surface area is \(4\pi r^2\). (This and previous arguments can be made precise with the modern language of integral calculus.)
Dividing a sphere into many pyramids connected to the center allows us to relate the sphere's surface area and volume.
Here’s an elegant way to rephrase this result: The surface area of a sphere is equal to the area of the curved portion of a cylinder that exactly encloses the sphere. In fact, something very surprising happens here!:
Archimedes’ Hat-Box Theorem: If we draw any two horizontal planes as shown below, then the portions of the sphere and the cylinder between the two planes have the same surface area.
Any two horizontal planes cut off a band on the sphere and another band on the enclosing cylinder. Archimedes' Hat-Box Theorem says that these bands have the same area. (The planes shown here have heights \(0.4\cdot r\) and \(0.6\cdot r\) above the equator.)
We can prove this with (all!) the methods in the last few posts; here’s a quick sketch. To compute the area of the “spherical band” (usually called a spherical zone), first consider the solid spherical sector formed by joining the spherical zone to the center:
The Hat-Box theorem can be proved by relating the area of the spherical zone to the volume of this spherical sector.
By dividing this into lots of triangular pyramids as we did with the sphere above, we can compute the area of the spherical zone by instead computing the sector’s volume. This volume can be computed by breaking it into three parts: two cones and the spherical segment between the two planes (on the left of the next figure). Compute the volume of the spherical segment by comparing (via Cavalieri’s Principle) to the corresponding part of the vase (from the previous post), which can be expressed with just cylinders and cones.
Computing the volume of a spherical segment via Cavalieri's Principle
Last week we saw how to compute the area of a circle from first principles. What about spheres?
To compute the volume of a sphere, let’s show that a hemisphere (with radius \(r\)) has the same volume as the vase shown in the figure below, formed by carving a cone from the circular cylinder with radius and height \(r\). Why this shape? Here’s why: if we cut these two solids at any height \(h\) (between 0 and \(r\)), the areas of the two slices match. Indeed, the slice—usually called cross section—of the sphere is a circle of radius \(\sqrt{r^2-h^2}\), which has area \(\pi(r^2-h^2)\). Similarly, the vase’s cross section is a radius \(r\) circle with a radius \(h\) circle cut out, so its area is \(\pi r^2-\pi h^2\), as claimed.
When sliced by a horizontal plane at any height \(h\), the hemisphere and vase have equal cross-sectional areas. (Shown here for \(h = 0.4\cdot r\).) By Cavalieri's Principle, this implies that they have equal volumes.
If we imagine the hemisphere and vase as being made from lots of tiny grains of sand, then we just showed, intuitively, that the two solids have the same number of grains of sand in every layer. So there should be the same number of grains in total, i.e., the volumes should match. This intuition is exactly right:
Cavalieri’s Principle: any two shapes that have matching horizontal cross sectional areas also have the same volume.
So the volumes are indeed equal, and all that’s left is to compute the volume of the vase. But we can do this! Recall that the cone has volume \(\frac{1}{3} (\text{area of base}) (\text{height}) = \frac{1}{3}\pi r^3\) (better yet, prove this too! Hint: use Cavalieri’s Principle again to compare to a triangular pyramid). Likewise, the cylinder has volume \((\text{area of base}) (\text{height}) = \pi r^3\), so the vase (and hemisphere) have volume \(\pi r^3 – \frac{1}{3} \pi r^3 = \frac{2}{3}\pi r^3\). The volume of the whole sphere is thus \(\frac{4}{3}\pi r^3\). Success!
The following visualization illustrates what we have shown, namely $$\text{hemisphere} + \text{cone} = \text{cylinder}.$$ The “grains of sand” in the hemisphere are being displaced horizontally by the stabbing cone, and at the end we have exactly filled the cylinder.
Stabbing a cone into a hemisphere made of horizontally-moving "sand particles" exactly fills a cylinder.
