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!
$\begingroup$
$\endgroup$
asked Feb 7, 2021 at 7:41
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
Yes.
OXXXX
XXOOO
XOXOO
XOOXO
XOOOX
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$– WhatsUpFeb 7, 2021 at 8:00
$\begingroup$
$\endgroup$
2
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
answered Feb 7, 2021 at 7:54
-
$\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$– bobbleFeb 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