1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

Yes.

OXXXX
XXOOO
XOXOO
XOOXO
XOOOX

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

$\endgroup$
2
  • $\begingroup$ You got it! We can actually do better than $3n-3$ in general. See oeis.org/A072567 $\endgroup$ – Dmitry Kamenetsky Feb 7 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 at 8:00
1
$\begingroup$

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

$\endgroup$
2
  • $\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 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$ – Rand al'Thor Feb 7 at 15:50

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.