Bathroom floor tiles

Question

Recently I was looking at the tiles on my bathroom floor. They are small square tiles about a square cm each arranged in a grid. They come in two colors, the majority of them are a light brown while a select few of them are a darker brown. Since the color scheme of my bathroom is pretty awful we'll just call them black and white (with white being the more abundant color).

While I was looking at the tiles I was looking for four tiles that formed a the points of a parallelogram. To my dismay there were none (I spent much more time than I care to admit verifying this fact). So I started a new game, I would try to see what tiles I could make black without disturbing this property. Soon I began to wonder how many tiles I could could be black in my bathroom while maintaining this property. I found this a pretty daunting task because there quite a few tiles in my bathroom, so I downsized. First I worked it out with 1 by 1 and 2 by 2 bathrooms. These were pretty easy you can fit 1 tile in a 1 by 1 and 3 in a 2 by 2. 3 by 3 is a little more difficult I was able to determine 5 tiles could be fit.

Proof:

Let us for a moment just consider the following parallelograms:

(the parallelograms with corners in the top and bottom row)

This will require at least 2 white tiles in these rows to break all of these parallelograms, and unless there are more than 2 we need one in the center column. We can make an identical argument for the first and last columns, meaning that we need at least 3 white tiles in the outer ring (corners can be shared between the columns and row but centers cannot).

Originally I made a more complex argument involving a lot of the parallelograms here, but I think it is a little more appropriate to brute force it from here. Here are all the ways that we can have three white tiles that satisfy the properties stipulated above:

I have shaded the parallelograms that can be made from black tiles in red. As we can see all 3 of the possibilities fail.

Since none of these pass we know that there are at least 4 white tiles. Luckily for us I found some solutions with 4 white tiles that do work so we can stop here:

---

This proof does not scale up to 4 or larger squares very well or at all. It feels barely more elegant brute forcing the problem and I fear that it would take me hours to come up with a proof on a 4 by 4.

As Rahul pointed out and Jaap Scherphuis expanded upon we can create a lower bound for the number of black tiles that can fit on the floor at $2n-1$ (or $m+n-1$ for rectangular floors) by filling in two of the edges. Jaap was kind enough to do a programatic search and found that this lower bound is optimal up to $7\times 7$, however no one has yet proven that $2n-1$ is the best for all squares.

What methods might I use to solve larger or general cases of this problem?
Is the lower bound always the best way?

Answer 1

I wrote a simple program to do a brute force search for the patterns with the maximal number of black tiles without a parallelogram. I only tried up to $7 \times 7$, because it is rather slow when it gets to that size.

In a comment above, Rahul pointed out that the $3\times 3$ solution with the top row and first column black is also a general solution for any rectangle size. This means that for an $m\times n$ rectangle, we can have at least $m+n-1$ black tiles.

My program has not found any better solutions (up to $7 \times 7$). I do not have proof that this holds for larger rectangles/squares. There are quite many solutions, and most but not all have at least one row or column black. It is fairly easy to see that once you have a completely black row/column, you can only add at most one black tile in each other row/column, because else you have 4 black tiles in a rectangle.

There is a general solution that does not have a whole black row/column, and that is the solution where the top row and left column is black except for the top left corner, and the bottom right corner is also black. I have not examined the solutions very closely to see if there are any other ones that generalize.

If degenerate parallelograms (i.e. with the four tiles in a straight line) are also disallowed, then the general solutions described above do not work when one of the dimensions is $5$ or more. It seems that in that case there is no solution with $m+n-1$ black tiles. I suspect that the maximum number of tiles is then around $3(m+n+1)/4+1$ (i.e. if a dimension is increased by 4, you can only add 3 more tiles) but I have nothing concrete to base that on.

Here's my source code, in C#.

  using System;
  using System.Collections.Generic;

  namespace test4
  {
     /*
      * Colour as many squares as possible of an HxW grid without producing a parallelogram
      * May or may not call 4 in a line a parallelogram.
      */
     internal class Parallelogram
     {
        // size of rectangle
        private const int W = 7;
        private const int H = 7;

        // set to false if also disallow degenerate parallelograms
        private const bool allowLineOf4 = true;

        private static readonly List<int[]>[] parallelograms = new List<int[]>[H * W];

        public static void Main()
        {
           CreateParas();
           bool[] board = new bool[H*W];
           int best = 0;
           Search(board, 0, 0, ref best);
        }

        private static void CreateParas()
        {
           for (int i = 0; i < H*W; i++)
           {
              parallelograms[i] = new List<int[]>();
           }
           for (int p1 = 0; p1 < H*W; p1++)
           {
              for (int p2 = p1+1; p2 < H * W; p2++)
              {
                 for (int p3 = p2 + 1; p3 < H * W; p3++)
                 {
                    int x1 = p1 % W;
                    int y1 = p1 / W;
                    int x2 = p2 % W;
                    int y2 = p2 / W;
                    int x3 = p3 % W;
                    int y3 = p3 / W;
                    int x4 = x2 + x3 - x1;
                    int y4 = y2 + y3 - y1;
                    if (x4 >= 0 && x4 < W && y4 >= 0 && y4 < H && (!allowLineOf4 || (x1 - x2) * (y2 - y3) != (y1 - y2)*(x2 - x3)))
                    {
                       int p4 = x4 + W*y4;
                       int[] para = { p1, p2, p3, p4 };
                       Array.Sort(para);
                       parallelograms[para[3]].Add(para);
                    }
                 }
              }
           }
        }

        private static void PrintBoard(bool[] brd)
        {
           for (int y = 0; y < H; y++)
           {
              for (int x = 0; x < W; x++)
              {
                 Console.Write(brd[x + y * W] ? "X" : ".");
              }
              Console.WriteLine();
           }
           Console.WriteLine();
        }

        private static void Search(bool[] brd, int ix, int count, ref int best)
        {

           if (ix >= brd.Length)
           {
              if (count >= best)
              {
                 if (count > best)
                 {
                    Console.WriteLine("---- " + count);
                    best = count;
                 }
                 PrintBoard(brd);
              }
              return;
           }
           if (brd.Length - ix + count < best) return;

           brd[ix] = true;
           if (IsOK(brd, parallelograms[ix]))
           {
              Search(brd, ix + 1, count + 1, ref best);
           }
           brd[ix] = false;
           Search(brd, ix + 1, count, ref best);
        }

        private static bool IsOK(bool[] brd, List<int[]> paras)
        {
           foreach (int[] para in paras)
           {
              if (brd[para[0]] && brd[para[1]] && brd[para[2]] && brd[para[3]]) return false;
           }
           return true;
        }
     }
  }