Rose VII: Odd Isometric Rules

Last time, we proved that the “four colored points in a row” rule can never reach the optimal ¾ coloring in isometric space. Yet somehow, the odd rules are optimal like clockwork.

We’ve got two main directions to go in, at this point. We can look at the simpler odd rules and try to prove that every odd rule has an optimal coloring, or we could look at the complicated even rules and try to find out why they don’t work as well, and try to figure out efficient colorings for them. Let’s do the former in this post.

Warning, there’s a dry-ish proof coming. It’s not thaaaat difficult to follow, but admittedly that’s coming from the guy who wrote it. I’ll try to be extra precise and descriptive, and will illustrate the steps as much as possible.

Rose VI: Even and Odd Rules in Isometric Space

Last time, we proved that 1/3 colored was the best you could do on an isometric grid, if your rule was “two colored points in a row are not allowed”. And that’s pretty interesting – it’s already very different from the squares we’re used to. So, let’s so how different other rules are.

The next logical rule to try is “three colored points in a row are not allowed”, so let’s jump in and try our old staircase technique on it. (The colored points are a light yellow, so it’s a little easier to see them.)

I just shifted each row over by one relative to the previous row, and it just works. Our technique didn’t work on the first rule we tried, but somehow it works on this one. We get a nice 2/3 coloring, and it’s very easy to prove it’s the most optimal coloring – 2/3 is the highest percent of any row you can color, so it’s the upper bound for how much of the space can be colored.

So the question here is – when does our shifting technique work, and when do we need to use some other technique / cleverness to get the optimal coloring? Let’s try the next rule, “four colored points in a row are not allowed”.

And as you can see, it just doesn’t work. I tried staggering the next row by different amounts, but they all don’t line up in one of the three directions. It’s interesting that both colorings are perfect in two of the three directions – looking at the patterns left to right and along one diagonal, they’re perfectly three-colored-one-uncolored in a row. But along the other diagonal, there’s one row of alternating colored-uncolored, and then a row of all colored (which breaks the rule).

This doesn’t necessarily mean that the rule doesn’t have a coloring that is ¾ colored, it just means that we haven’t found it. Before we delve too deep into this rule, let’s look at the next rule – some context of surrounding, similar problems often gives strong insight into a tough nut to crack.

And just like that, the next rule has a provably optimal coloring. All the diagonals work out, and you can kind of see that this is the isometric analogue to a square staircase.

So, a pattern is starting to emerge here. Rules with an odd number of colored points in a row seem to work out nicely, and rules with an even number of points don’t. I did a few more, to make sure the pattern held.

Let’s zoom back in on the “four colored points” rule case. The next logical thing I can think of to try is to try staggering the ¾ row in other ways. If ¾ colored is possible, it’s made of ¾ colored rows, so maybe we can stagger those rows in the right way to find a coloring. This turned out to be a pretty messy case-by-case proof, which I’ve summarized here.

The basic idea is to build up every possible way to stagger the pattern of three-colored-one-uncolored in rows to make the diagonals work out. Anytime a case leads to a situation where you can’t use the three-colored-one-uncolored pattern, you know that that case can’t ever produce a ¾ colored coloring.

I wrote out the first line, and then there are four different ways to stagger the next line, but the later two are just the first two flipped, so there’s two ways this pattern can start. Then, we break each of those into two cases, based on the existence of a particular colored point in the third row. As you can see, if that point, indicated by a red triangle, is in the final pattern, it means that there must be two uncolored points in the fourth row, so neither of those cases can achieve ¾ coloring. If those red points are uncolored, it turns out both of those cases also have two out of four points in the fourth row uncolored.

And so, with this very messy proof, we’ve proved that the optimal coloring of an isometric space with the rule “four colored points in a row is not allowed” can’t ever reach the theoretical maximum of ¾! More on that next time!

Rose V: Square Wrap-Up and Isometric!

We’ve made a lot of progress on the Rose problems! Last time, we proved that given a rule of the form “N colored points in a row is not allowed”, we have optimal colorings for all square-grid spaces for as many dimensions as we want! That may sound pretty specific, but let’s take a broader look at just how many cases that covers.

I’m imagining sorting all possible rules into three different categories. They are: rules that prohibit only colored points, like “Three colored points in a row are not allowed”, rules that prohibit only uncolored points, like “Three uncolored points in a row are not allowed”, and rules that have some combination of those rules, like “an uncolored point between two colored points is not allowed”. Sidenote: If you remember from the Rose II definition, I decided to phrase all rules as negative, as “XYZ is not allowed”, because positive rules, like “you must have a colored point between two uncolored points” vanish as we go to infinity, or can be rephrased as negative rules.

If you think about these three categories, you’ll realize that we just solved the first one, for square grids of N dimensions, and the latter two are trivial: color the whole space and you’ll get an optimal coloring that won’t ever need an uncolored point for the rules to apply to.

What I’m saying is, give me a square grid of any dimension and any single 1D rule you can think of, and I can find and prove what the optimal coloring is!

But before we get to the more complicated “multiple rule” cases, let’s look at some alternatives to regular integer spaces. Namely, the isometric space!

This is a beautiful, interesting space. The purple triangles represent the points, and each point has six neighbors! The 2D square grid has two “directions” in which rules can be broken and adds a direction whenever you add a dimension. The 2D isometric grid has three directions from the get-go: one depicted horizontally here, and two on the 60° and 120° diagonals. And it’s even more interesting in other dimensions – I can sort of visualize a 3D isometric space, but it’s not clear to me if it’s well-defined or even exists in higher dimensions!

Let’s jump right in, as usual. For square grids, the easiest, quickest rule has been “Two colored points in a row are not allowed”. Let’s try our techniques on this new space.

And somehow, alternating colored points on the first row sort of… doesn’t work. Doing it means the entire next row must be uncolored. We can repeat this process on the next few rows to get a total of ¼ of the space colored. We can tell that it’s ¼ because of the trick we used for the square grids – find a tile that repeats. The red outlined parallelogram can be used to tile the whole pattern, and it’s ¼ colored, so the space is ¼ colored.

Then, I tried spacing them out more evenly, to get this configuration. It gets us 1/3 of the space colored, using the red outlined parallelogram.

After I found that one, I tried and tried and couldn’t find one that worked better. Maybe this is the best we can do in the isometric space. So then I went about trying to prove it when I hit upon this tile.

A simple, triangular tile, which you can alternate to cover every point in the space. But under our rules, the most colored that this tile can be is 1/3. If we color two points, that means there are two adjacent colored points, and that’s not allowed. And because this tile can tile the entire space, that means that the most colored the space can be is 1/3 colored!

So, we’ve proven that the 1/3 colored space above is the best you can do. We’ve done this by coming up with a space that is 1/3 colored, making 1/3 the lower bound, and using the pigeonhole principle to show that there can’t be anything better. If someone tells me they have a better fraction, I can break the space into these triangles with three points in them, and show that their coloring must have at least one triangle that has more than one colored point!

Next time we’ll look at some other rules for the isometric space, which is already looking much more complex than the square grids we’ve solved! With the rule we solved for today, we got ½ of the square grid colored easily!

Interlude: Pokemon Hexagons

Happy Celebration of Mind Day! In the spirit of Martin Gardner, let's do some mathematics that's as approachable and intuitive as possible.

Let's take a little break from the Rose problems and talk about Pokemon. Love the games to this day, especially all the self-imposed challenges you can do. So, I was very excited to see graphics of Pokémon stat spreads as hexagons in an article recently, and of course it immediately got me thinking of a math problem.

For those of you who don’t know much about Pokémon, all species of Pokémon have “base stats”, which are measures of their competency in various areas. Each Pokémon has a stat for HP (Hit Points), Attack, Defense, Special Attack, Special Defense, and Speed. Base stats don’t seem to necessarily have an upper limit, but the highest existing base stat is Blissey’s 255 Base HP. There are a lot of other factors that determine a Pokémon’s actual stats, but we’re only concerned about their base stats for this problem.

The question that immediately came to my mind was, which Pokémon has the stat hexagon with the most area? Which Pokémon have a lot of area despite poor stats?

Here’s some example Pokémon hexagons. The first three are Abra, Kadabra, and Alakazam – an evolutionary line of Pokémon focused on Speed and Special Attack. Below them are Rhyhorn and Rhydon, an evolutionary line focused on HP, Attack, and Defense. And on the right we see Mew and Mewtwo, the legendary Pokémon from Generation I.

The order of the stats around the hexagon are important: Rhydon has a sizeable chunk of area because its HP, Attack, and Defense are all high and they’re right next to each other. (The order was decided by the article, and I kept the same it to answer my original question.) Obviously Pokémon with higher stats, like fully evolved Pokémon and legendaries, will have hexagons of larger area. But how should we distribute stats to get the most possible area?

It was at this point that I made a guess. I don’t know many of the newer Pokémon nearly well enough to make a great guess, but my intuition told me that something with very unbalanced stats would be the best shot at getting a high area. I went with Rhyperior, Rhydon's evolution, as the non-Mega non-legendary Pokémon with the most area, because it has gargantuan Attack, Defense, and HP, but next to nothing in the other three stats.

Now that I have a guess, let’s get to solving the problem. Let’s start by expressing it mathematically: you have six nonnegative radial lengths defining a hexagon. You also have a limitation that the sum of these lengths must equal a given constant. What radial lengths can you choose to optimize the area of the final hexagon?

This particular kind of hexagon is easy to find the area of, luckily. You can break it into triangles along the radial lines, and add up the areas of the six triangles for the area of the hexagon. Even more conveniently, we can use the 1/2(ab sin(C)) equation for a triangle’s area, which spits out a very convenient formula for us to maximize: (1/2)(sin 60)(ab + bc + cd + de + ef + fa). We can ignore the constant, because 2x will always be greater than 2y if x > y, so that leaves us with (ab + bc + cd + de + ef + fa), or the sum of adjacent products of base stats. Attack x Defense, Defense x HP, HP x Special Attack, and so on.

Now, how do we maximize this? Let’s try some test cases. I’ll use 600 as the base stat total, both because it’s conveniently divisible by six and because it is the actual base stat total of several Pokémon.

Case 1: Straight 100s across the board. The area of the hexagon (before the constant) is 60,000.

Case 2: 150, 50, 150, 50, 150, 50. The area is only 45,000.

Case 3: 50, 50, 50, 150, 150, 150. The area is 65,000. We’re getting warmer!

Case 4: 0, 0, 0, 200, 200, 200. The area shoots up to 80,000!

Case 5: 0, 0, 0, 0, 300, 300. The area maxes out at 90,000!

Case 6: 0, 0, 0, 0, 200, 400. We’re back to 80,000, which means we have our answer.

It turns out that a Pokémon with only Attack and Defense would have a greater hexagon area than any other distribution of its stat total! The way to maximize the sum of adjacent products of a list of six is to make two of the numbers as large as possible, and equal! Does this work with an arbitrarily large or small set? What if you used products of three numbers, like (abc + bcd + cde + ...)? Most importantly, it means my intuition was right, kinda!

I crunched the numbers (and made a little Excel tool for viewing any Pokémon’s hexagon, as well as its total area), and I was close, if not exactly right. The first non-legendary of the list, is Slaking, with a base stat total greater than most legendaries. Then there’s Garchomp, Metagross, Goodra– Pokémon known for being solid all around with maybe one exceptional stat. A heap of legendaries later, Rhyperior, the 15^th non-mega non-beast non-legendary on the list. Feels like I’m having to invent rules to be right, but I’m still gonna round that up to a win. J