Rose III: 3-Dimensional Staircases

Phew, back to the good stuff. Let’s talk about higher dimensions – 3, 4, and eventually N dimensions – and how the Rose problem works with them. Right now we know that in our two-dimensional world, a rule of “four colored points in a row is not allowed” yields an optimal coloring that looks like a bunch of staircases, that I immediately named the Staircase Configuration. As a first step into higher dimensions, let’s see if the same problem (four colored points in a row is not allowed) in three dimensions can be solved by a staircase analogue.

Sidenote: the Fundamental Theorem of Geometry is in full effect for this post. For anyone who needs a refresher, the Fundamental Theorem of Geometry is that 3D things are hard to visualize. We’ll also be using the Strong Fundamental Theorem of Geometry, which is that difficulty of visualization scales with the number of dimensions, in the next post.

Okay, so we’re in three-dimensions and our rule is that four colored points in a row is not allowed. My best idea as to how to tackle three dimensions is somehow build up from the 2D solution we had before.

 Let’s say that this, our 2D solution, is one plane of the 3D solution. This might seem like a bit of a leap, but remember that the 1D solution is one line of the 2D solution. In fact, it’s all the lines, only a bit staggered. Will that method work with the 2D to 3D jump?

Turns out, yes it will! These four cross-sections should be visualized in a stack, the leftmost one on the bottom and the rightmost one on top. I’ve only drawn out sixteen points for each, but they represent an entire plane of points, extending infinitely in two directions. So, you can see that they’re identical; I’ve just “staggered” them, shifting the next plane over by one point.

Each plane by itself cannot break the rule of “four colored points in a row is not allowed”; they are the 2D solutions, after all. Now we only have to check the z-direction – the direction that crosses one point on each of these planes. For example, imagining this example as a 4x4x4 cube, we can check the top left point on each plane. The fifth plane up is identical to the first, so we can see the familiar pattern of colored, colored, colored, uncolored. And checking each and every point in this cube, we can see that they all work! In fact, if you slice the cube into four planes in any of the other ways, the planes will all be identical to our 2D solution!

So, 3D staircases work! At least for this case – let’s check the other simple rules: three-in-a-row is not allowed, and two-in-a-row is not allowed.

      

They may be a little harder to visualize, but they work too! Now, for a 3D space with a rule of “N-in-a-row is not allowed”, we want to prove that staircases work for them, too. And it’s not that difficult – we’ve proven that a staircase works for 2D, and by staggering those 2D cases so there’s a total of N incremental staggers before it loops back to the original staircase, we have a provably sufficient staircase. A “stagger” really just builds up a vertical tower of the row you’re staggering along, and because the row abides by the rule, every vertical tower built up by staggering a 2D space will abide by the rule as well.

We’ll tackle 4D and N Dimensions next time!