Correct solutions were received from Juan Carlos Marivela, Philippe Fondanaiche, Lou Cairoli, Paul Botham.

As was pointed out by several correspondents, this problem bears a remarkable similarity to POTW 120, posed about two years ago.  No, this was not by design, I had simply forgotten about the previous problem.  ( I knew this would happen eventually!) 

In any case, it is impossible to color the 3 ´ 7 and the 5 ´ 5 grids without creating a monochromatic rectangle.  The 4 ´ 6 grid, however, admits the following solution:

See the solution to problem 120 for the 3 ´ 7 case.  

For the 5 ´ 5 case, you can argue as follows.  Consider the coloring of the first row of the grid.  There is one color, say B, occurring at least three times. In the remaining four rows of these three columns, two Bs may never appear in the same row since otherwise a monochromatic rectangle colored B would result.  There are only four possible colorings of these three columns in the last four rows using at most one B, namely BRR, RBR, RRB, RRR.  If RRR does not occur, then one of the other colorings must appear twice, giving a monochromatic rectangle labeled R.  On the other hand, it is obvious that if RRR does appear, a monochromatic rectangle colored R cannot be avoided.

An interesting additional question is:  What is the smallest possible number of monochromatic rectangles in a 3 ´ 7 grid?, in a 5 ´ 7 grid? 

You are visitor number  3749 to this page.