Counting Cards

Over the past few days my roommate and I have been working on a business card Menger sponge origami project. This was most recently inspired by Thomas Hull‘s fun book ‘Project Origami‘, but it’s quite possible I’d heard of the project before I found the book. I know that in Hull’s book he finds formulas for the number of cards it takes to make various iterations of the sponge, but I wanted to try to come up with them again on my own, and thought I’d share my process.

Let $F_n$ be the number of cards showing on each face of a level $n$ sponge (recalling that level 0 is just an ordinary cube). The exterior faces of the Menger sponge are Sierpinski carpets, and it’s pretty easy to determine that $F_0=1$ and $F_n=8\cdot F_{n-1}$ . This means $F_n=8^n$ .

Next, let $U_n$ be the number of cards needed to make a completely unpanelled level $n$ sponge. So $U_0=6$ , and to make a level $n$ sponge requires 20 level $n-1$ sponges, so $U_n=20\cdot U_{n-1}$ . This makes $U_n=20^n\cdot 6$ .

Now I’d like to determine the number of cards needed for what I’ll call ‘interior panelled’ sponges. Let $I_n$ denote the number of cards for such a level $n$ sponge. A level $n$ sponge consists of lots of little cubes, some of the faces of which are showing (not stuck against faces of other little cubes). Some of the showing faces occur on the very exterior of the sponge (on the faces of the encompassing cube, if you want). So ‘interior panelled’ would be all of the faces except these very exterior ones. There’s no such thing as an interior panelled level 0 sponge, so we start at level 1, counting $I_1$ as follows: Begin with an unpanelled level 1 sponge ( $U_1=20\cdot 6$ cards), and panel the two interior faces of each of the 12 ‘edge’ level 0 cubes. So $I_1=U_1+2\cdot 12=20\cdot 6 +2\cdot 12=144$ .

What about the next iteration for $I_n$ ? Well, there are 20 ‘interior panelled’ $n-1$ sponges, and you need to panel 2 of the exterior faces of each of the 12 ‘edge’ cubes. The exterior faces, recall, require $F_{n-1}$ cards to panel. So $I_n=20\cdot I_{n-1}+2\cdot 12\cdot F_{n-1}$ . Since we know $F_{n-1}=8^{n-1}$ , we can clean this formula up a little: $I_n=20\cdot I_{n-1}+24\cdot 8^{n-1}$ .

Now we’re almost done. The overall goal is to have a fully panelled level $n$ sponge. Let $P_n$ denote the number of cards required. Since a fully panelled level $n$ cube is an interior panelled level $n$ cube, along with exterior panelling, it’s easy to count. There are 6 exterior faces, each requiring $F_n=8^n$ cards to panel, so $P_n=I_n+6\cdot 8^n$ .

So we’re down to two formulas:

$\begin{array}{rcl}I_n &=& 20\cdot I_{n-1}+24\cdot 8^{n-1} \\ P_n &=& I_n+6\cdot 8^n\end{array}$

At this point, I checked Hull’s book, and noticed he had only one formula – one for $P_n$ . So how do we get rid of $I_n$ ?

Solve the second equation for $I_n$ , obtaining $I_n=P_n-6\cdot 8^n$ (and so also $I_{n-1}=P_{n-1}-6\cdot 8^{n-1}$ ). Now substitute these two formulas in their appropriate places in the formula above for $I_n$ . This gives

$P_n-6\cdot 8^n=20(P_{n-1}-6\cdot 8^{n-1})+24\cdot 8^{n-1}$

which we simplify to

$P_n=20\cdot P_{n-1}-6\cdot 8^n,$

obtaining the formula that Hull’s book has (hurray!).

Perhaps there’s something more than can be done to understand this formula though (and Hull does have remarks like this as well). I’d really like my recurrence formula for $P_n$ to have $(n-1)$ s showing up, instead of that $n$ in the power for 8. So write $P_n=20\cdot P_{n-1}-6\cdot 8\cdot 8^{n-1}$ . How can we interpret this formula geometrically, in terms of the sponge? Well, we see that to make a panelled level $n$ sponge, we make 20 level $n-1$ sponges, and then remove some bits. In particular, we remove the panelling on faces of cubes that come together – that’s where the $8^{n-1}$ comes from, it is, after all $F_{n-1}$ , the number of panels on a face of an $n-1$ sponge. How many faces come together? Well, each of the 8 corner cubes (that lonely 8 in $6\cdot 8\cdot 8^{n-1}$ ) is 3-valent, meaning there are three ‘edges’ hitting that cube. At each of these 3 edges, we have two ( $3\cdot 2=6$ , in $6\cdot 8\cdot 8^{n-1}$ ) panelled faces coming together, and we must remove all of that panelling.

So there you have it – a formula for the number of cards to build a level $n$ Menger sponge. If you’re interested in building one, start gathering up cards. While the level 0 sponge (a cube) requires only 12 cards, a level 1 sponge already requires 192 cards. The level 2 sponge, that my roommate and I built, took 3456 cards, and the next level would require a staggering 66,048 cards. I’m in no hurry to start making one of those.

About these ads

Tags: menger sponge, origami, recursive, sequence

This entry was posted on January 3, 2009 at 5:47 pm and is filed under Play. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

∑idiot's Blog

Counting Cards

Like this:

Leave a Reply Cancel reply

Follow “∑idiot's Blog”