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!

Hexprimes I

I was invited to attend Gathering 4 Gardner this year (FINALLY!) and had a blast. Every single person I met was utterly fascinating in their own right – I met an unlikely number of interesting people! And, I was lucky enough to be able to give a talk at Gathering 4 Gardner, which was (to my surprise) well-received. I was afraid my half-baked musings would be too simple for that caliber of mathematician, but it turns out that they place a lot of value on something being understandable for someone of all skill levels. So here’s a brief discussion of the talk I gave!

-----------------------------------------------------------------------------------------------------------------------

A prime number is a number whose only divisors are 1 and itself. I’ve been thinking about different ways to define prime numbers, and here’s another definition that is completely legitimate: A prime number is the area of an integer-sided rectangle whose length or width must be 1. In the picture below, we can see that 12 is not a prime, because it can be written as a 6x2 or a 4x3 rectangle. 13 is a prime, because it can only be in an 13x1 rectangle.

And voila! Our new definition gives us something to manipulate and explore. What happens if we change “rectangle” to “triangle” or “hexagon”? What kinds of things are triprimes, or hexprimes?

A few considerations about technique and assumptions first. The defining characteristic of a rectangle as opposed to other quadrilaterals is that rectangles are equiangular, so I kept the triangles and hexagons equiangular as well. Rectangles are also very easy to break down the area of – triangles and especially hexagons are not quite as easy to break down. So I use a circle-packing metric in the place of area: for squares I use circles packed in a square grid, and for triangles and hexagons I use an isometric grid.

So, triprimes turn out to be kinda boring. Equiangular triangles are equilateral, so the only numbers that can be expressed as a triangle at all are, of course, the triangle numbers (1,3,6,10,15,21,…). The concept of the triangle numbers literally arose from this fact. So there’s a bunch of very predictable tricomposites (composites because their expressions do not have sides of length 1) and not really any triprimes. Like I said, boring.

Hexprimes, on the other hand, are fascinating. The equiangular constraint leaves plenty of wiggle room for interesting hexagons to form for each possible area. Some of those hexagons are diagrammed below. Note, they all have at least one tiny side, meaning they’re all prime.

And then we get to 7, the first hexcomposite. This hexagon with area 7 has no sides of length 1, which means it’s a hexcomposite. No smaller number is a hexcomposite!

Now that we know that both hexprimes and hexcomposites exist, it’s only natural to ask what other numbers are hexprimes and hexcomposites. It turns out that finding new hexcomposites is a bit different than finding regular composites. With rectangles, you can just double a rectangle and put them together to create another rectangle that must be a composite. You can’t combine an arbitrary hexagon with itself to create another hexagon. No, you have to increase by rows, like shown below.

And it turns out you can do this in a lot of different ways.

So, expressions for hexcomposites converge very quickly. With these hexagons, I can show that any number > 17 must be a hexcomposite! And that means that there are a finite number of hexprimes, and we can find them easily by checking the cases below 18. And, drum roll please – there are exactly 10 hexprimes! 2, 3, 4, 5, 6, 8, 9, 11, 15, and 17!

A final note – triprimes are very restrictive, and imminently predictable. Hexprimes are less restrictive, but composite-finding techniques converge quickly, so they are predictable as well. Give me any positive number, and I can very quickly tell you if it’s a triprime or a hexprime. But the middle ground, “rectangular” primes, AKA regular old prime numbers, are still infrequent and infinite enough to be unpredictable!