SOLUTION: what is the smallest number of cells that need to be coloured in a 5 by 5 square so that any 1 by 4 or 4 by 1 rectangle lying inside the square has at least one cell coloured.
Algebra ->
Polynomials-and-rational-expressions
-> SOLUTION: what is the smallest number of cells that need to be coloured in a 5 by 5 square so that any 1 by 4 or 4 by 1 rectangle lying inside the square has at least one cell coloured.
Log On
Question 1192533: what is the smallest number of cells that need to be coloured in a 5 by 5 square so that any 1 by 4 or 4 by 1 rectangle lying inside the square has at least one cell coloured. Found 2 solutions by greenestamps, ikleyn:Answer by greenestamps(13200) (Show Source):
Obviously, if any row or column contains no colored cells, then you can place a 1x4 or 4x1 rectangle in that row or column without covering any colored cells. So to start with, you need at least 5 of the cells to be colored, with one cell in each column and one cell in each row colored. There are many ways you can do that. As examples....
+---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+---+
| X | | | | | | | X | | | | | | | X | | |
+---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+---+
| | X | | | | | X | | | | | | X | | | | |
+---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+---+
| | | X | | | | | | X | | | | | | | X | |
+---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+---+
| | | | X | | | | | | | X | | | | | | X |
+---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+---+
| | | | | X | | | | | X | | | | X | | | |
+---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+---+
Whatever way you choose those first five cells to be colored, there are four colored cells that are either in row 1 or 5 or in column 1 or 5. That means there are four places you can place a 1x4 or 4x1 rectangle without covering a colored square -- two columns and two rows.
By placing another colored cell at each of the two intersections of those two rows and those two columns, you eliminate all the places where a 1x4 or 4x1 rectangle could have been placed without covering a colored cell. Using the above examples....
+---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+---+
| X | | | | Y | | | X | | | | | | | X | | |
+---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+---+
| | X | | | | | X | | | Y | | | X | | | | Y |
+---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+---+
| | | X | | | | | | X | | | | | | | X | |
+---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+---+
| | | | X | | | | Y | | | X | | | | Y | | X |
+---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+---+
| Y | | | | X | | | | | X | | | | X | | | |
+---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+---+
So the smallest number of colored cells that make any 1x4 or 4x1 rectangle cover at least one colored cell is 5+2=7.
