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!


2 Answers 2




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

  • $\begingroup$ You got it! We can actually do better than $3n-3$ in general. See oeis.org/A072567 $\endgroup$ Feb 7, 2021 at 7:50
  • $\begingroup$ Thanks for the link. I knew the projective plane interpretation since very long ago. There are some more interesting results in the linked page. $\endgroup$
    – WhatsUp
    Feb 7, 2021 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

enter image description here

  • $\begingroup$ 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. $\endgroup$
    – bobble
    Feb 7, 2021 at 15:07
  • $\begingroup$ @bobble Oops. My list of sets was right, but somehow I clicked the wrong cells in the picture when making the diagonal. Fixed. $\endgroup$ Feb 7, 2021 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.