# 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.

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.

• You have shown that $51$ can be colored and no more than $52$ can be colored. It may be there is a better proof which shows no more than $51$ can be colored. It may be that you did not find the optimal coloring and there is one with $52$ squares. It may be that the proof that no more than $51$ can be colored cannot be explained simply and one just has to catalog the cases. – Ross Millikan Jan 29 at 3:03
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 and $$1\le j_1. This "no-good" constraint prevents all four squares in a rectangle from being colored.