Maximal tiling without any 3-in-a-rows

You are given an arbitrarily large grid, where each square can either be off or on (think Game-of-life type board).

You need to tile such a grid to maximize the number of "on" squares without there being any 3-in-a-row of "on" squares. A 3-in-a-row can be horizontal, vertical, or diagonal. 3-in-a-row of "off" squares are allowed.

The best tiling I could come up with is

101010101010
101010101010
010101010101
010101010101

which gives a ratio of 1/2. The best upper bound I have is 6/9 (as you can't fit 7 on any non-wrapping 3x3 square). I believe the optimal solution will be periodic, but if it isn't then that is OK.

Is the tiling above the optimal tiling? Can this problem be generalized to N-in-a-row?


You can achieve 5/9 density by infinitely tiling this pattern horizontally:

010101
110110
101010

This does not however tile the plane.

I also did an exhaustive search for 3x6, and found that 10/18 was optimal. Any tiling of the plane with a greater density of 10/18 must contain blocks of 3x6 with more than 10 squares on. This is impossible, thus 5/9 is an upper bound on the density.

EDIT: The best bound I've found through exhaustive search is 13/24. No better density is possible.

However @feersum conjectured that for any finite size field $n+1 \over 2n$ is always possible, which if true makes exhaustive search a fruitless effort to prove the bound 1/2 tight.


The upper bound can be tightened considerably by looking at 13x13 squares, where the best possible pattern is 86, giving an upper bound of 86/169 $\approx$ 0.5088

Edit: and slightly more with 15x15, which give 114/225 $\approx$ 0.5067