Now, it’s time to tackle those annoying even rules. Unlike the
odd rules, they don’t play nice. I wasn’t able to find proofs or perfect
colorings like I could with the other rules – it took a long, inelegant,
case-by-case proof to show that ¾ coloring isn’t possible for the “four colored
points in a row” case. It's summarized in this earlier post in flowchart form, if you're intensely curious. Here, I'm only going to explain how and why the standard technique doesn’t work.
Throughout these problems, our technique for coloring as
much as possible has always been this: color as many as you can along one axis,
leave one point uncolored, color as many as you can again, repeat. Then, do the
same thing on the next row, but start a few points over, so you don’t have two
uncolored points in a row in the other direction. That’s the technique that can
never work for an even isometric rule.
The best way to explain this is to try it. Let’s say we pick
some stagger, and we plan to repeat that stagger to get the best coloring for an
even rule “n colored points in a row”. Now, the number of spaces you stagger it
by must be relatively prime to n. Look at the example below, where the rule is
n=4 (“4 colored points in a row is not allowed”) and the stagger is 2.
The stagger will never put an uncolored point in rows 1 and
3, so we have to use a stagger of 1 or 3, because they’re relatively prime to
4. But that doesn’t work either. Look at this same picture another way. A
stagger of 2 in that direction is a stagger of 3 in this direction, and this direction
works.
When you pick a stagger for the next line, you’re actually
picking a stagger pair. The stagger in the two directions will always have a difference
of 1, just due to the geometry of the isometric grid. And these two numbers
have to be relatively prime to your n. And of course, of two consecutive
numbers, one must be even, so you can never have a repeating stagger for an
even rule. Odd rules work just fine, because they can be prime, and even if
they aren’t, the stagger pair 1 and 2 will always be relatively prime with an odd
number (which, non-coincidentally, was the stagger pair I used for the proof
last time).
That’s a pretty important finding. The geometry of the grid
prevents us from using that technique for even rules. As for other techniques, like varying
the stagger per line, I haven’t had much success. I proved that a ¾ coloring isn’t possible with a rule of n = 4, but that doesn’t tell us
that we can’t get very close to it.
So we’re left with the task of finding a decent lower bound
for the even rules. The consistent bounds I found were just the optimal solutions
for the n-1 rule case: the provably optimal solution to “five points in a row”
is pretty good for “six points in a row”. I also tried a few interesting ideas,
taking suboptimal staggers like the one above and leaving some extra points
uncolored to make them follow the rules, and those squeezed out tiny improvements
over the earlier bounds. The “four colored points” rule has the lower bound of
2/3 borrowed from the “three colored points” rule, but there’s a configuration
with three rows of ¾ and one row of ½, which is 11/16 colored, making it a
little better than our bound.
This is a really interesting coloring. Notice how there's a colored-colored-uncolored-uncolored pattern in every fourth diagonal, and in the rows it's a colored-uncolored-colored-uncolored pattern, which come together to satisfy the condition everywhere. There's definitely some good problem ore here, no matter how much tedious work it's buried behind.
But for now, here are my final conclusions on the Isometric Rose problems.
Odd rules can be proven to have an optimal coloring given by a (1,2) stagger,
with (n - 1)/n % of the space colored. Even rules may not have optimal
colorings, and have weak lower bounds of (n - 2)/(n – 1) % of the space
colored. Until next time, when I will hopefully have a new problem to talk about!
