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.
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      -&gt; 1     -&gt; 1 1   -&gt; 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.