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!

The Vertices of a Cube

I recently got a couple of tiny wooden cubes – and by a couple, I mean about 250. They’re wonderful for visualizing all sorts of interesting problems about cubes and discrete 3-space. So, with a bunch of cubes in hand, I set about imagining some problems. I came up with three problems, all about the vertices of cubes, and here they are.

Problem 1

In my initial “problem searching” wandering, I drew the numbers 1 through 6 on the cube, with pairs adding up to seven on opposite sides like a standard die. Then I noticed that each of the eight vertices had three adjacent numbers, and I started to think about the eight different sets of numbers represented by the vertices. What if I could choose a number for each face, but each of those eight sets had to have the same sum? What would my choices be limited to?

This problem proved to be quite simple. Two adjacent vertices, as shown in the diagram, share two elements of their three element set. 

The vertex on the left has the sum A + B + D, and the vertex on the right has the sum A + B + C. If these sums had to be the same, then A + B + D = A + B + C, so D = C. Now, because of symmetry, we know that all opposite faces must have the same value. We didn’t assume anything; we just started with two arbitrary vertices, and you can verify that if we pick two vertices in a different adjacent direction, it leads to proving that the two faces oriented in that direction are equal. And it turns out, that’s it! Every vertex is a combination of a x-oriented, y-oriented, and z-oriented face, and if faces with the same orientation have the same value, then every vertex is the sum of those three numbers! The only restriction on this cube is that opposite faces must have the same value!

Problem 2

Then, of course, I asked myself the reverse question. What if each of the vertex sums had to have a different value? Moreover, what is the optimal cube that satisfies this property? My intuition told me that there were probably many cubes that fit the description, so I needed to find a “best” one. Maybe one whose sums were all consecutive numbers, or one whose total sum was the lowest possible. So I decided to limit myself to positive integers.

I started by lazily finding an upper bound. I like powers of two, so I started with the good old 1, 2, 4, 8, 16, 32. The sum of any three of them can’t equal the sum of any other three, because if you write the sum in binary, you get a number with three ones and three zeroes, with the ones like flags pointing towards which numbers were in the sum. Not all of these sums would be present, because of the geometry of cubes, but it would easily pass the condition as long as none of the sets of three had the same faces, which of course they didn’t. So the lazy upper bound for total sum was 63. Didn’t have a great way to quantify an upper bound for how close the sums were, so I ignored it for now.

Then, I made myself a little adjacency map of a cube’s faces and vertices, so it would be easier than turning a cube around in my hands and losing track of what was where. This went through a few iterations before I settled on this one – it’s simple, somewhat symmetric, and keeps most of the properties of the three-dimensional model. The areas are the faces, and the other areas they touch are are the faces they’re adjacent to. If only the earth was a cube – maps would be way more fun.

Then, I outlined what the optimal cube would look like. The smallest possible sum of three positive integers was three, and there were eight vertices, so the best possible sums would be 3, 4, 5, 6, 7, 8, 9, and 10. Well, I thought, let’s jump right in and see if that’s possible.

I started with the three ones, necessary to have a sum of three.

I would also need a sum of 4, so I added a 2 on another face. I can pick any face without losing generality, because the cube is still symmetric and all remaining blank faces have identical properties.

Now, I need a 5. You can only get a 3 with 1+1+1, and you can only get a 4 with 1+1+2, but you can get a 5 with either 1+2+2 or 1+1+3. Anyone familiar with Kakuro should know the score by now. Luckily, adding a 2 to either blank space ends in another 1+1+2 situation, which breaks our only rule. We can’t have two different vertices adding up to 4, after all. So if this mythical perfect cube exists, it must have a 3 in one of these two remaining faces. And the map of the cube itself shows you that the two remaining faces have symmetry, so we can pick whichever we like to put the 3 on.

As you can see, that 3 neatly gets us the 6, too. The next number we need is 7, and we have two ones bordering the last face, so if we’re to get a 7, it must be 5. If the perfect cube exists, this face must be a 5, and we have to hope that the rest of the vertices work out to be different somehow.

And amazingly, they work out perfectly. The perfect cube with all unique vertex sums does exist, and it’s not only definitely the cube with the lowest sum, but all of its sums are adjacent! I thought I was going to find a contradiction and have to trudge through a slew of messy cases to find the optimal cube, but there was no need.

Problem 3

The final question of the three came from a completely different angle, almost literally. One of the cubes had an imperfection, a little chip off of a vertex. As I studied it, I thought about the triangle formed when slicing off a vertex of a cube. As I imagined all the ways you could cut a vertex, it occurred to me that there was something strange. None of these triangles were obtuse, and only the most extreme edge cases were right triangles! But there wasn’t much of a limitation – I tried to imagine a good way to phrase the problem without the context of a cube, and this is what I came up with. If you have a triangle with one point on the x-axis, one point on the y-axis, and the final point on the z-axis, can this triangle be obtuse?

I haven’t proven this one yet. My intuition tells me it’s not possible, without offering any theoretical basis for that claim. I can fix two of the points and see what the angles look like when the third point goes to infinity, and it always seems to approach a right triangle or a line, but that’s not exactly a rigorous proof.