# No four cells forming a rectangle

You are given a 5x5 square grid with 25 cells. Can you paint 12 cells, such that no 4 painted cells form the corners of a rectangle with sides parallel to the edges of the grid? Good luck!

Yes.

OXXXX
XXOOO
XOXOO
XOOXO
XOOOX


This extends to any $$n \times n$$ grid, on which you can paint $$3(n - 1)$$ cells.

• You got it! We can actually do better than $3n-3$ in general. See oeis.org/A072567 – Dmitry Kamenetsky Feb 7 at 7:50
• Thanks for the link. I knew the projective plane interpretation since very long ago. There are some more interesting results in the linked page. – WhatsUp Feb 7 at 8:00

Same method as for this previous similar question:

• Put labels $$A, B, C, D, E$$ along the top for each column, then label the rows by certain subsets of the set $$\{A, B, C, D, E\}$$.

• 5 rows, so 5 different subsets.

• 12 painted cells, so the sizes of all subsets sum to 12.

• No rectangles, so no pair of subsets has two elements in common.

How can we do this? For example,

$$\{A,B\}$$, $$\{A,C\}$$, $$\{A,D\}$$, $$\{A,E\}$$, $$\{B,C,D,E\}$$, which gives

• I only see 11 painted cells in your picture, and the question asks for 12. I think painting R1C5 would give you a legal twelfth. – bobble Feb 7 at 15:07
• @bobble Oops. My list of sets was right, but somehow I clicked the wrong cells in the picture when making the diagonal. Fixed. – Rand al'Thor Feb 7 at 15:50