Give a 13x13 square table. Colour S squares in the table such that no four coloured squares are the four vertices of a rectangle. Find maxS.

Question

Give a 13x13 square table (like this)

Colour S squares in the table such that no four squares are the vertices of a rectangle.

Find the maximum value of S.

I have tried Calculate in Two Ways like this.

Let T be the set of pairs of cells (A, B) such that both A and B are coloured and on the same row.

As no four coloured squares are four vertices of a rectangle, every two columns have one pairs in T at most. Hence, $ \vert T \vert \leq \binom{13}{2} = 78$

Let $a_{1}, a_{2}, a_{3}, ..., a_{13}$ be the number of colour squares on row $1, 2, ..., 13$. We have: $$\vert T \vert = \sum_{i = 1}^{13} \binom{a_{i}}{2} = \sum_{i=1}^{13} \dfrac{a_{i}^2}{2} - \dfrac{S}{2} \geq \dfrac{\dfrac{1}{13} S^{2} - S}{2} $$

It can be obtained that $ \dfrac{1}{13} S^{2} - S \leq 156 \Rightarrow S \leq 52$

Equality holds on when $a_{1} = a_{2} = ... a_{13} = 4$ and every pairs of columns have one pairs of cell in T.

However, I can only colour 51 squares satisfying the problem.

Please help me.

Edit : Actually , if we do the same way for columns, S = 52 holds on when there are 4 coloured squares on each column and each pair of rows must have exactly two coloured squares on a column.

Answer 1

The maximum is 52, as shown in OEIS A072567. Here's a coloring that achieves that maximum:

I used integer linear programming, as follows. Let binary decision variable $x_{i,j}$ indicate whether square $(i,j)$ is colored. The problem is to maximize $\sum_{i,j} x_{i,j}$ subject to $$\sum_{i\in\{i_1,i_2\}} \sum_{j\in\{j_1,j_2\}} x_{i,j} \le 3$$ for all $1\le i_1<i_2 \le 13$ and $1\le j_1<j_2 \le 13$. This "no-good" constraint prevents all four squares in a rectangle from being colored.

Answer 2

To construct an example for S = 52, note that (a) permuting the rows and columns of a colouring doesn't change the property of not containing a rectangle; (b) since $\binom{13}2 = 13\cdot\binom42$, every possible choice of two cells in a row/column must be represented.

This allows us to systemically list the 2-combinations of rows and columns and arrange them (with a little bit of trial and error) into the desired colouring. My chosen algorithm yields the colouring below: