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!

Rose II: Signposts and Necessary Evil

The problem I discussed in the last post, the first of the inaptly named Rose problems, was just a small, very specific case of a big general problem. When I first discover a seemingly rich vein of problem ore, there appear to be hundreds of directions to dig in. Who knows which direction I have to dig in to get the best problem gems (the hardest ones, if you will); it’s only after you find some that you start to get an understanding of the layout of the deposit. So, I’m going to try digging in a bunch of directions, trying to see what I can find.

First, let me restate the problem, as generally as I can. You have some kind of discrete infinite space, and an infinite number of tokens to place on points, and there are rules about configurations of adjacent tokens that aren’t allowed, and your task is to cover the largest possible percentage of the space.

Now, I’ve solved this for the specific case of the discrete infinite space being an infinite 2D checkerboard, and for the rules being “you can have only 1 or 3 tokens in a row horizontally or vertically”. The solution to that case is that 75% of the space, and the proof is in Rose I. 

-----------------------------------------------------------------------------------------------------------------

The next thing to do is list a few promising directions to dig in, and then go explore them. Here goes.

Problem variable manipulations – we’ve solved it for a specific case, but let’s think about the heart of the problem so we can see how many specifics there really was.

•        We could try solving the same problem in 3, 4, or N dimensions.
•        We could change the rules (of what configurations aren’t allowed).
•        We could add the concept of multi-dimensional rules (such as a two by two square of tokens are not allowed)
•        We could change the layout of the grid to isometric / other more complicated tilings
•        Etc. I’m sure we’ll think of more as we get deeper in.

Rule Obsolescence – Oddly enough, it looks like the rule “you’re not allowed to have exactly two tokens in a row” in Rose I didn’t matter at all. If we re-allow that, the end result doesn’t change. That means that given a set of rules, some of them may be made obsolete by the others – and that sounds like it’s worth exploring.

Alternate Coverings – There might be many equally efficient ways to cover a space; how many? Are they isomorphic to the original, or are they new and unique?

----------------------------------------------------------------------------------------------------------

Finally, a note on terminology before I conclude this post. Yeah, I know; this is the awful part, the fatal flaw that prevents a mainstream love for math. But I promise it’ll be quick. I’m sure you already know that it’s necessary.

A Rose Problem considers some discrete N-dimensional space, and asks what is the maximum percentage of that space that can be covered (colored, as you’ll see in a moment), subject to certain rules.

To make things more fundamental, let’s switch from the “tokens covering a chessboard” metaphor to one of points and colors. Discrete spaces are made of Points, and points can be Colored instead of covered with a token. So I might say that 75% of this space can be colored, given the rules. Also, this opens up the possibility of multiple colors used on a space, and that could lead to some interesting optimizations.

Finally, Rules are patterns of colors that are not allowed in the final coloring of the space. I’ve been thinking of rules as negative (as in, you’re not allowed to use this particular pattern) rather than positive (as in, you must use this pattern), and I think it makes sense to keep it that way. Positive rules won’t matter as we go to infinity, unless we impose some sort of regularity to it (such as, in every 10x10x10 cube, this pattern must exist once), and that feels horribly contrived.

Phew. That’s it. More good stuff and less necessary evil in the next post.

Three-In-A-Row (Rose I)

Imagine your garden-variety infinite chessboard, with an accompanying infinite number of tokens. Now, imagine your task is to cover as much of the board as possible with tokens, one token to a space, but there are two accompanying rules. You’re not allowed to have more than three tokens in a row horizontally or vertically, and you’re not allowed to have exactly two tokens in a row horizontally or vertically. That is, these configurations are allowed:

And these are not.

This is the form that this problem originally took for me. It happened when I was playing with the placement of apps on my phone’s home screen; I’d be willing to bet that 90% of these interesting problems I think of originate from some mundane task in my life.

In any case, let’s try to solve the problem. Given these placement rules, what is that maximum percent of the plane that you can cover?

I started by trying some simple configurations, as usual. This was a good base case that established an easy lower bound.

It’s not difficult to see that this layout covers 50% of the plane – every other space is covered. So then I improved it slightly, by trying one of the ugly phone app configurations still allowed by the rules.

For this one it’s a little harder to tell how much of the plane this covers, but if you look at the 4 x 4 square outlined in red, you can see that the entire plane is made of tiles of that square. 9/16 of that tile is covered, so we’re up to 56.25% of the plane covered as our lower bound. (You can actually put the 4x4 square anywhere because of how tilings work!)

And finally I hit upon this pattern, which I immediately named the Staircase configuration.

Staircase covers a nice 75% of the plane, and it looks like it’s packed very tightly. And as it turns out, it’s provably optimal! I'll spoiler the proof here, in case you want to work it out for yourself.

My proof is pretty simple. Let’s hop down to one dimension. You have an infinite one-dimensional chessboard, which is just a row of squares, and you have the same rules as before. It seems pretty obvious that you can’t do better than this configuration, which is 75% of the plane.

And if 75% coverage is the best you can do for any single row of the two-dimensional chessboard, that means the best you can do for the entire chessboard is 75% as well!

Of course, there’s many many more problems waiting to be uncovered here. When I find a potentially rich vein of problem ore, I immediately give it a name that does not age well, and often ends up being completely irrelevant to the fully explored problem. So, let’s continue that tradition by naming this set of problems Rose problems, a corruption of “rows.” Three-in-a-row, rows, Rose. A terrible, annoyingly catchy name, which is an essential bit of character for a dry math problem set. I’m sure there’s much more to come on the Rose problems soon enough!

Hexprimes I

I was invited to attend Gathering 4 Gardner this year (FINALLY!) and had a blast. Every single person I met was utterly fascinating in their own right – I met an unlikely number of interesting people! And, I was lucky enough to be able to give a talk at Gathering 4 Gardner, which was (to my surprise) well-received. I was afraid my half-baked musings would be too simple for that caliber of mathematician, but it turns out that they place a lot of value on something being understandable for someone of all skill levels. So here’s a brief discussion of the talk I gave!

-----------------------------------------------------------------------------------------------------------------------

A prime number is a number whose only divisors are 1 and itself. I’ve been thinking about different ways to define prime numbers, and here’s another definition that is completely legitimate: A prime number is the area of an integer-sided rectangle whose length or width must be 1. In the picture below, we can see that 12 is not a prime, because it can be written as a 6x2 or a 4x3 rectangle. 13 is a prime, because it can only be in an 13x1 rectangle.

And voila! Our new definition gives us something to manipulate and explore. What happens if we change “rectangle” to “triangle” or “hexagon”? What kinds of things are triprimes, or hexprimes?

A few considerations about technique and assumptions first. The defining characteristic of a rectangle as opposed to other quadrilaterals is that rectangles are equiangular, so I kept the triangles and hexagons equiangular as well. Rectangles are also very easy to break down the area of – triangles and especially hexagons are not quite as easy to break down. So I use a circle-packing metric in the place of area: for squares I use circles packed in a square grid, and for triangles and hexagons I use an isometric grid.

So, triprimes turn out to be kinda boring. Equiangular triangles are equilateral, so the only numbers that can be expressed as a triangle at all are, of course, the triangle numbers (1,3,6,10,15,21,…). The concept of the triangle numbers literally arose from this fact. So there’s a bunch of very predictable tricomposites (composites because their expressions do not have sides of length 1) and not really any triprimes. Like I said, boring.

Hexprimes, on the other hand, are fascinating. The equiangular constraint leaves plenty of wiggle room for interesting hexagons to form for each possible area. Some of those hexagons are diagrammed below. Note, they all have at least one tiny side, meaning they’re all prime.

And then we get to 7, the first hexcomposite. This hexagon with area 7 has no sides of length 1, which means it’s a hexcomposite. No smaller number is a hexcomposite!

Now that we know that both hexprimes and hexcomposites exist, it’s only natural to ask what other numbers are hexprimes and hexcomposites. It turns out that finding new hexcomposites is a bit different than finding regular composites. With rectangles, you can just double a rectangle and put them together to create another rectangle that must be a composite. You can’t combine an arbitrary hexagon with itself to create another hexagon. No, you have to increase by rows, like shown below.

And it turns out you can do this in a lot of different ways.

So, expressions for hexcomposites converge very quickly. With these hexagons, I can show that any number > 17 must be a hexcomposite! And that means that there are a finite number of hexprimes, and we can find them easily by checking the cases below 18. And, drum roll please – there are exactly 10 hexprimes! 2, 3, 4, 5, 6, 8, 9, 11, 15, and 17!

A final note – triprimes are very restrictive, and imminently predictable. Hexprimes are less restrictive, but composite-finding techniques converge quickly, so they are predictable as well. Give me any positive number, and I can very quickly tell you if it’s a triprime or a hexprime. But the middle ground, “rectangular” primes, AKA regular old prime numbers, are still infrequent and infinite enough to be unpredictable!