12
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 3-in-a-row means both vertically and horizontally, but not diagonally, right? $\endgroup$ – quapka Nov 27 '15 at 14:40
  • $\begingroup$ @quapka "A 3-in-a-row can be horizontal, vertical, or diagonal." $\endgroup$ – Nathan Merrill Nov 27 '15 at 14:41
  • $\begingroup$ I am just blind, thanks :) $\endgroup$ – quapka Nov 27 '15 at 14:42
  • $\begingroup$ I've thought about this problem before. There turns out to be only one way to do it (optimal or non-optimal, and even if you allow non-periodic solutions), not counting obvious symmetries like rotations, flips, and swapping 0 and 1. $\endgroup$ – Jack M Jan 9 '16 at 11:22
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @randomra, if the maximum Hamming weight which can be achieved in an $m\times n$ rectangle is $w$ then that gives an upper bound for the density of any infinite tiling of $\frac{w}{mn}$ by the simple mechanism of superimposing an $m \times n$ grid over the infinite tiling. $\endgroup$ – Peter Taylor Jan 15 '16 at 19:06
  • $\begingroup$ My bad, I confused it with a lower bound. $\endgroup$ – randomra Jan 15 '16 at 19:18
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Doesn't this mean that there is an upper limit of 8/12 (not inclusive), and a lower limit of 7/12 (inclusive)? $\endgroup$ – Nathan Merrill Nov 27 '15 at 15:51
  • 1
    $\begingroup$ Actually, I don't think this tiling works. There is a 3-in-a-row starting with the top left corner going up/left. $\endgroup$ – Nathan Merrill Nov 27 '15 at 15:53
  • 1
    $\begingroup$ Just as for your 6/9: Tile the plane with 3x4. If the average is more than 7/12, then at least one 3x4 contains 8 on lights. $\endgroup$ – Empy2 Nov 27 '15 at 15:54
  • $\begingroup$ Yes, as I say it does not extend to an unbounded array, I just gave an upper bound of 7/12, and showed why the 3x4 does not immediately give 6/12 as an upper bound. $\endgroup$ – Empy2 Nov 27 '15 at 15:55
  • $\begingroup$ I understand, my bad. $\endgroup$ – Nathan Merrill Nov 27 '15 at 15:56
-2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I don't understand the argument that cases can be eliminated by the symmetry of swapping 0s and 1s: that's not a symmetry, because 000 is allowed and 111 isn't. I also don't understand what contradiction you see in your first example. $\endgroup$ – Peter Taylor Jan 9 '16 at 11:53
  • $\begingroup$ @PeterTaylor Oh, I see, I thought this was basically a sort of infinite tic tac toe, with no three-in-a-rows of either kind allowed. Well, I'll leave my answer up. Probably with some more case analysis a similar method would yield an answer to this question. $\endgroup$ – Jack M Jan 9 '16 at 11:54
  • 1
    $\begingroup$ The existence of (non-tiling) moderately large squares with densities > 1/2 (e.g. 15x15 with 114 bits set) indicates that the case analysis would have to work on larger units than those squares. I very much doubt that the number of cases for this type of approach would be computationally tractable. $\endgroup$ – Peter Taylor Jan 9 '16 at 12:09
  • $\begingroup$ If it is true that my tiling in my question is optimal, then it would, interestingly, work with your additional restriction as well. $\endgroup$ – Nathan Merrill Jan 9 '16 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.