2
$\begingroup$

Give a 13x13 square table (like this) A 13x13 square table example

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

A not satisfied example

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. enter image description here

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Jan 29 at 3:03
2
$\begingroup$

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

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How to colour like this ? Is it just about luck ? I find the equality in some combinatorics problems really difficult ? $\endgroup$ – Kiên Phùng Hữu Jan 29 at 8:28

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.