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!
