The problem I discussed in the last post, the first of the
inaptly named Rose problems, was just a small, very specific case of a big
general problem. When I first discover a seemingly rich vein of problem ore, there
appear to be hundreds of directions to dig in. Who knows which direction I have
to dig in to get the best problem gems (the hardest ones, if you will); it’s
only after you find some that you start to get an understanding of the layout
of the deposit. So, I’m going to try digging in a bunch of directions, trying
to see what I can find.
First, let me restate the problem, as generally as I can.
You have some kind of discrete infinite space, and an infinite number of tokens
to place on points, and there are rules about configurations of adjacent tokens
that aren’t allowed, and your task is to cover the largest possible percentage
of the space.
Now, I’ve solved this for the specific case of the discrete
infinite space being an infinite 2D checkerboard, and for the rules being “you
can have only 1 or 3 tokens in a row horizontally or vertically”. The solution
to that case is that 75% of the space, and the proof is in Rose I.
-----------------------------------------------------------------------------------------------------------------
The next thing to do is list a few promising directions to
dig in, and then go explore them. Here goes.
Problem variable manipulations – we’ve solved it for a
specific case, but let’s think about the heart of the problem so we can see how
many specifics there really was.
- We could try solving the same problem in 3, 4, or N dimensions.
- We could change the rules (of what configurations aren’t allowed).
- We could add the concept of multi-dimensional rules (such as a two by two square of tokens are not allowed)
- We could change the layout of the grid to isometric / other more complicated tilings
- Etc. I’m sure we’ll think of more as we get deeper in.
Rule Obsolescence – Oddly enough, it looks like the rule
“you’re not allowed to have exactly two tokens in a row” in Rose I didn’t
matter at all. If we re-allow that, the end result doesn’t change. That means that
given a set of rules, some of them may be made obsolete by the others – and
that sounds like it’s worth exploring.
Alternate Coverings – There might be many equally efficient
ways to cover a space; how many? Are they isomorphic to the original, or are
they new and unique?
Finally, a note on terminology before I conclude this post. Yeah, I
know; this is the awful part, the fatal flaw that prevents a mainstream love
for math. But I promise it’ll be quick. I’m sure you already know that it’s
necessary.
A Rose Problem considers some discrete N-dimensional
space, and asks what is the maximum percentage of that space that can be
covered (colored, as you’ll see in a moment), subject to certain rules.
To make things more fundamental, let’s switch from the
“tokens covering a chessboard” metaphor to one of points and colors. Discrete
spaces are made of Points, and points can be Colored instead of
covered with a token. So I might say that 75% of this space can be colored,
given the rules. Also, this opens up the possibility of multiple colors used on
a space, and that could lead to some interesting optimizations.
Finally, Rules are patterns of colors that are not
allowed in the final coloring of the space. I’ve been thinking of rules as
negative (as in, you’re not allowed to use this particular pattern) rather than
positive (as in, you must use this pattern), and I think it makes sense to keep
it that way. Positive rules won’t matter as we go to infinity, unless we impose
some sort of regularity to it (such as, in every 10x10x10 cube, this pattern
must exist once), and that feels horribly contrived.
Phew. That’s it. More good stuff and less necessary evil in
the next post.
