Three-In-A-Row (Rose I)

Imagine your garden-variety infinite chessboard, with an accompanying infinite number of tokens. Now, imagine your task is to cover as much of the board as possible with tokens, one token to a space, but there are two accompanying rules. You’re not allowed to have more than three tokens in a row horizontally or vertically, and you’re not allowed to have exactly two tokens in a row horizontally or vertically. That is, these configurations are allowed:

And these are not.

This is the form that this problem originally took for me. It happened when I was playing with the placement of apps on my phone’s home screen; I’d be willing to bet that 90% of these interesting problems I think of originate from some mundane task in my life.

In any case, let’s try to solve the problem. Given these placement rules, what is that maximum percent of the plane that you can cover?

I started by trying some simple configurations, as usual. This was a good base case that established an easy lower bound.

It’s not difficult to see that this layout covers 50% of the plane – every other space is covered. So then I improved it slightly, by trying one of the ugly phone app configurations still allowed by the rules.

For this one it’s a little harder to tell how much of the plane this covers, but if you look at the 4 x 4 square outlined in red, you can see that the entire plane is made of tiles of that square. 9/16 of that tile is covered, so we’re up to 56.25% of the plane covered as our lower bound. (You can actually put the 4x4 square anywhere because of how tilings work!)

And finally I hit upon this pattern, which I immediately named the Staircase configuration.

Staircase covers a nice 75% of the plane, and it looks like it’s packed very tightly. And as it turns out, it’s provably optimal! I'll spoiler the proof here, in case you want to work it out for yourself.

My proof is pretty simple. Let’s hop down to one dimension. You have an infinite one-dimensional chessboard, which is just a row of squares, and you have the same rules as before. It seems pretty obvious that you can’t do better than this configuration, which is 75% of the plane.

And if 75% coverage is the best you can do for any single row of the two-dimensional chessboard, that means the best you can do for the entire chessboard is 75% as well!

Of course, there’s many many more problems waiting to be uncovered here. When I find a potentially rich vein of problem ore, I immediately give it a name that does not age well, and often ends up being completely irrelevant to the fully explored problem. So, let’s continue that tradition by naming this set of problems Rose problems, a corruption of “rows.” Three-in-a-row, rows, Rose. A terrible, annoyingly catchy name, which is an essential bit of character for a dry math problem set. I’m sure there’s much more to come on the Rose problems soon enough!