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.
So, we’re trying to prove that any rule of the form “n
colored points in a row is not allowed”, where n is a positive odd integer, can
be satisfied on a 2D isometric space with an optimal coloring, which means that
the same percentage of the plane is covered as in the 1D case. Namely, (n-1)/n.
That’s a mouthful already, isn’t it? Basically, if the rule
is odd, we’re proving that you can always find a 2D coloring that is as
efficient as the 1D coloring.
My technique for this proof is to come up with a coloring
for an arbitrary odd n, and prove that it doesn’t result in breaking the rule
in any of the three major directions. My coloring looks like this:
It’s the old familiar staircase stagger. The coloring uses
rows of (n-1) colored, 1 uncolored, and staggers each subsequent row, keeping
the uncolored point as close as possible without keeping it in the same line.
That’s the technique I’m claiming will work for any odd number rule. So, now I’ll
prove that it works for all three of the directions, which I’ll title —, /, and
\.
“—" (The horizontal direction): Because
we’re building up this coloring in rows of n-1 colored points followed by an uncolored
point, this is a given. By definition, this direction can’t break the rules in
any way.
“ \ “ (The top-left to bottom-right direction): Let’s
define a modified coordinate axis so we can talk about our points in greater
detail.
Yes, the y-axis is a little slanted, but it doesn’t make any
difference for our purposes. It’s just notation, so I can say “the point at
(2,1)” and you’ll understand which one I mean.
Now, we’re putting this system down on top of our coloring,
so we can define any point to be the origin. Let’s put the origin, (0, 0), on
an uncolored point. Based on our coloring, there should be an uncolored point
at (1, -1), (2, -2), (3, -3), and so on.
This should go all the way to (n+1, -(n+1)). And, we know
that along the horizontal rows, there is a pattern of n-1 colored, 1 uncolored.
Therefore, there should be an uncolored point at (0, -(n+1)). So, the y-axis
doesn’t break the rules between (0, 0) and (0, -(n+1)), because the uncolored
points are exactly n-1 points apart.
We can do the same exact process from the point (0, -(n+1)),
to prove that there’s an uncolored point at (0, -(2n+2)). We can also do that
same process backwards from (0, 0), proving that (0, n+1) is uncolored. Just
imagine taking n steps diagonally, from (0, 0) to (-1, 1), to (-2, 2) and so
on, and then a big leap n steps to the right , landing back on the y-axis. And
therefore, we can prove that the entire y-axis doesn’t violate the rule,
because there’s definitely one uncolored point every n steps along it.
And, we can easily apply this exact same logic to (1, -1),
stepping all the way to (1, -(n+1) -1), and then leaping back to the left to
show (1, -(n+1) -1) is uncolored.
And there's nothing to stop us from doing this over the entire coloring. We can show that every single “\” diagonal doesn’t break the
rules with this technique!
“ / “ (The top-right to bottom-left direction): Let’s
define a new coordinate axis for this part of the proof. We could just use the
same one, but this one makes it a lot more convenient to see the proof work.
It’s exactly like the last one, but the y-axis is now lined
up with the new diagonal direction. Now, let’s define (0, 0) to be uncolored,
like before.
As you can see, that means that (2, -1), (4, -2), (6, -3),
and so on are all uncolored. The steps are a little different than in the last
part of the proof, but we can similarly show that (2(n+1), -(n+1)) is
uncolored. Then, we can use the definition of the horizontal pattern to move
back to the left, showing that (n+1, -(n+1)) and (0, -(n+1)) are also
uncolored. Finally, we can use the same technique we used in the last part of
the proof, showing that the entire y-axis cannot violate the rule.
But wait, something’s different. In the last part of the
proof, we could show that the same was true for points in other columns, like
(1, -1), (2, -2), etc. In this part of the proof, it’s not that simple, because
we only have uncolored points at (2, -1), (4, -2), etc. That means that we can
show that the rules aren’t broken in those columns, but we don’t know about the
column x = 1, or x = 3, and so on.
All we need to do is prove that there exists even one
colored point in each of these columns; if there is one, we can use the same
argument we used on the even numbered columns.
And now is where it’s important that n is odd. That means
that n and 2 are relatively prime! This part of the proof has a little group theory,
so I’ll explain it in brief here. Relatively prime means that two numbers don’t
have any factors in common, and that’s important here because the columns in
which there are uncolored points form a modulus function.
If you have a 12-hour clock, and you start at 12 and skip through
two hours at a time, you’ll go to 2, then 4, then 6, then 8, then 10, and then
12. You’ll never hit 5, because 12 and 2 are not relatively prime. On the other
hand, if you go through five hours at a time, you’ll hit 5, then 10, then 3,
then 8, then 1, 6, 11, 4, 9, 2, 7, and finally 12. You’ll hit every number
between 1 and 12, because they’re relatively prime.
I made a gif to illustrate this, but Blogger choked the life out of it. Hopefully it's still understandable.
Similarly, the points we’re looking at are advancing two
hours at a time on an n hour clock. That’s why we know there’ll be an uncolored
point at (1, -(n+1)/2), which will prove that the entire rest of the space, the
odd columns, don’t break the rule either!
Phew. That was a lot of proof in one post. But now we have
what we wanted – any odd rule in 2D isometric space has a proven optimal
solution!
