document.write( "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​. \n" ); document.write( "
Algebra.Com's Answer #824429 by greenestamps(13200)\"\" \"About 
You can put this solution on YOUR website!


\n" ); document.write( "ANSWER: 7

\n" ); document.write( "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....
\r\n" );
document.write( "\r\n" );
document.write( "   +---+---+---+---+---+   +---+---+---+---+---+   +---+---+---+---+---+\r\n" );
document.write( "   | X |   |   |   |   |   |   | X |   |   |   |   |   |   | X |   |   |\r\n" );
document.write( "   +---+---+---+---+---+   +---+---+---+---+---+   +---+---+---+---+---+\r\n" );
document.write( "   |   | X |   |   |   |   | X |   |   |   |   |   | X |   |   |   |   |\r\n" );
document.write( "   +---+---+---+---+---+   +---+---+---+---+---+   +---+---+---+---+---+\r\n" );
document.write( "   |   |   | X |   |   |   |   |   | X |   |   |   |   |   |   | X |   |\r\n" );
document.write( "   +---+---+---+---+---+   +---+---+---+---+---+   +---+---+---+---+---+\r\n" );
document.write( "   |   |   |   | X |   |   |   |   |   |   | X |   |   |   |   |   | X |\r\n" );
document.write( "   +---+---+---+---+---+   +---+---+---+---+---+   +---+---+---+---+---+\r\n" );
document.write( "   |   |   |   |   | X |   |   |   |   | X |   |   |   | X |   |   |   |\r\n" );
document.write( "   +---+---+---+---+---+   +---+---+---+---+---+   +---+---+---+---+---+

\n" ); document.write( "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.

\n" ); document.write( "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....
\r\n" );
document.write( "\r\n" );
document.write( "   +---+---+---+---+---+   +---+---+---+---+---+   +---+---+---+---+---+\r\n" );
document.write( "   | X |   |   |   | Y |   |   | X |   |   |   |   |   |   | X |   |   |\r\n" );
document.write( "   +---+---+---+---+---+   +---+---+---+---+---+   +---+---+---+---+---+\r\n" );
document.write( "   |   | X |   |   |   |   | X |   |   | Y |   |   | X |   |   |   | Y |\r\n" );
document.write( "   +---+---+---+---+---+   +---+---+---+---+---+   +---+---+---+---+---+\r\n" );
document.write( "   |   |   | X |   |   |   |   |   | X |   |   |   |   |   |   | X |   |\r\n" );
document.write( "   +---+---+---+---+---+   +---+---+---+---+---+   +---+---+---+---+---+\r\n" );
document.write( "   |   |   |   | X |   |   |   | Y |   |   | X |   |   |   | Y |   | X |\r\n" );
document.write( "   +---+---+---+---+---+   +---+---+---+---+---+   +---+---+---+---+---+\r\n" );
document.write( "   | Y |   |   |   | X |   |   |   |   | X |   |   |   | X |   |   |   |\r\n" );
document.write( "   +---+---+---+---+---+   +---+---+---+---+---+   +---+---+---+---+---+

\n" ); document.write( "So the smallest number of colored cells that make any 1x4 or 4x1 rectangle cover at least one colored cell is 5+2=7.
\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( " \n" ); document.write( "
\n" );