Puzzle #9 (Follow-up): Melting Fractals

The song “Let it Go” from the movie Frozen celebrates “frozen fractals.” I suppose a frozen fractal is something like the Koch snowflake.

Lately, though, one of my puzzles has made me more interested in melting fractals. The challenge of Puzzle #9 is to find structure in data that seems to be completely random. Here is the answer:

I posted the puzzle on the Brainteasers Forum at Wilmott.com, leading to a wide-ranging discussion that inspired me to investigate some melting fractals.

The Rooks Problem

Someone on the forum noted a connection between the puzzle and the rooks problem. The usual rooks problem is to find out how many ways you can arrange rooks on a regular chessboard without any of them threatening each other. Recall that rooks can move any distance either horizontally or vertically. A trivial solution is to place all the rooks on a main diagonal of the chessboard. In all, there are ways to solve the rooks problem.

Let’s take the rooks problem into three dimensions. In the 3D rooks problem, a cube (made of smaller cubes) replaces the chessboard. Along with their usual movements, we allow the rooks to move up and down like elevators between levels in the big cube.

Four rooks can occupy a cube without threatening each other. The image above suggests one solution: use the four small cubes that are full of data points. Let’s call these the “odd” cubes. The other solution is to use the four “even” cubes, which are empty in the picture.

Each solution for an  cube uses rooks. For an cube, each solution uses 64 rooks. How many solutions are there for the order-8 cube? At first, I thought the answer was about 1 quadrillion, but then I realized I was undercounting, and I wasn’t sure how to proceed.  Then I thought I could find the answer with Latin Squares.

Latin Squares and Latin Hypercubes

A Latin Square is an arrangement of symbols on a square grid so that each symbol appears exactly once in each row and in each column. Sudoku is a Latin Square with an additional constraint. I realized that a 3D rooks pattern could be mapped by a Latin Square. The rooks on the first level are marked by 1s, the second level by 2s, and so on. Here’s an example:

1     8     7     6     5     4     3     2
2     1     8     7     6     5     4     3
3     2     1     8     7     6     5     4
4     3     2     1     8     7     6     5
5     4     3     2     1     8     7     6
6     5     4     3     2     1     8     7
7     6     5     4     3     2     1     8
8     7     6     5     4     3     2     1

It is known that there are about 109 quadrillion solutions for the order-8 Latin Square, so that must also be the number of ways to arrange rooks in an order-8 cube.

There is a data sampling methodology called Latin Hypercube Sampling, an extension of Latin Squares into higher dimensions. Samples are only drawn from the cells in a selected Latin Hypercube pattern. This ensures that the samples are evenly distributed when examined along any single dimension. The tendency of Latin Hypercubes to resist clustering reminds of sampling with quasi-random numbers, which I wrote about here.

Melting Fractals

There is a simple recipe for the pattern in the image above: take a cube, then divide it into eight smaller cubes. There are alternating “odd” and “even” cubes. Remove the four even cubes, so that the four odd cubes remain. In this way we melt a cube into four small cubes whose combined volume is half that of the original cube (but with the same surface area).

What happens if we keep repeating this process on the new cubes? I speculated on the Wilmott forum that the remaining material would approach a Sierpinski Tetrahedron, a fractal made of small tetrahedra in a self-similar pattern. It turns out that I was right (but not original). Here is a video I made with MATLAB that shows the cube melting down:

From some vantage points, you can see that all of the little cubes appear to form a square (if you must know, it’s a Latin Square in distances from the viewer instead of in numbers or symbols).  As the process repeats on smaller and smaller cubes, you can see a Sierpinski Tetrahedron emerge. At the midpoint of the video, the process reverses so that you can watch the tetrahedron crystallize back into a cube.

The color of each cube is determined by its location. The x-y-z coordinates of a cube’s center are the red-green-blue components of its color.

Fractal Dragons

Let’s say that an “even (odd) melt” removes all the even (odd) cubes. All the melts in the video above are even melts.

What if we alternated even and odd melts? The next video begins the same way as the first video, with an even melt at the first stage. In the second stage, however, all the melts are odd. We continue to alternate, leading to a spindly fractal that reminds me of dragon curves:

You might notice that some new colors appear that weren’t present in the first animation.

Fractal Clouds
We disagreed on the Wilmott forum about whether we could end up with a disconnected fractal. I argued that the fractal would always be connected. I was wrong about that. The last video shows that random melting can lead to disconnected clouds.

 

Copyright 2014.  All Rights Reserved.