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!
