Maximal tiling without any 3-in-a-rows

Question

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?

Answer 1

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

Answer 2

An upper limit of $7/12$ from considering $3\times4$ rectangles.
If there are eight on lights, then each of four columns has two on lights. There are only a few ways to fill the middle two columns, and each of them prevents too many lights in the outer columns.
Seven in 12 can be done (but does not extend to an unbounded array):
1010
1011
0101

Answer 3

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.

Answer 4

Optimal or non-optimal, periodic or non-periodic, there's essentially only one way to do this.

Suppose we have an assignment of 0s and 1s to each cell on the infinite grid, not necessarily a tiling (ie. not necessarily periodic), and not necessarily optimal. The trick is to play a kind of Sudoku to show that there is an essentially unique way to do this.

There must be a 1 somewhere in the grid. Now, to the right of this 1, we have three possibilities: either we have 0 0, 0 1, or 1 0. Notice that the case 1 0 is isomorphic to the case 0 0, since in the former case we would have 1 1 0 and in the latter we would have 1 0 0, which are the same thing under the symmetry of flipping the board horizontally and swapping 0s and 1s. So we have only two cases: 1 0 0, and 1 0 1.

Suppose first that there's a 1 0 0 somewhere on the board. We need another case study: either the cell immediately under it is 1, or it is 0. I'll show how you can use the "sudoku" to get a contradiction out of the first assumption:

1 0 0     1 0 0    1 0 0    1 0 0
1      -> 1     -> 1 1   -> 1 1 0   Contradiction!
          0        0        0   0

If the cell immediately under it is 0, then we have the pattern

1 0 0
0

If we try applying the sudoku method to deduce the rest of the grid, we find that we don't run into any contradictions, and indeed we start generating an infinitely tiling pattern:

1 1 0 0
0 0 1 1

You can show that if the grid contains this 2x3 pattern, and there are no three-in-a-rows, then this pattern must tile infinitely in all directions. This completes the case study for when the grid contains a 1 0 0.

Now suppose we have a 1 0 1 somewhere on the grid. Again we have to do a case study: we have either

1 0 1
0

or

1 0 1
1

In either case, calculating outwards as usual, you pretty quickly find the fatal 2x6 pattern mentioned above (possibly rotated 90°), so that's that.