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.

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): You can put this solution on YOUR website!

ANSWER: 7

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.

Answer by ikleyn(52803)   (Show Source): You can put this solution on YOUR website!
.

I managed to solve the problem with the lesser number of colored squares, 6.

+---+---+---+---+---+ | | | X | | | +---+---+---+---+---+ | | X | | | | +---+---+---+---+---+ | X | | | | X | +---+---+---+---+---+ | | | | X | | +---+---+---+---+---+ | | | X | | | +---+---+---+---+---+

ANSWER.     6.

RELATED QUESTIONS
Every asterisk in the question 2*0*1*5*2*0*1*5*2*0*1*5 = 0 is to be replaced by either +... (answered by KMST)
What is the smallest two-digit number that gives a remainder of 1 when divided by 2, 3,... (answered by chessace)
What is the smallest whole number that has a remainder of 1 when divided by 4, a... (answered by RAY100)
The red blood cell counts (in millions of cells per microliter) for a population of (answered by Boreal)
Hi, i've been having a lot of trouble slving this any help would be nice! In order to... (answered by kev82)
a) For any prime p>=5, prove that p2+2 ( P square +2) is composite or not. b) Find the... (answered by venugopalramana)
Suppose a cell divides one time each minute. The number of cells over time:... (answered by stanbon)
1. Find the least perfect square number divisible by 3,4,5,6 & 8? 2. Find the least no.... (answered by jsmallt9)
What is the radius of the smallest circle that surrounds a 5-by-12... (answered by greenestamps,ikleyn)

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​.

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.