Conference rusure::math

1134.0. "Non-chromatic Rectangles..." by DWOVAX::YOUNG (We CAN do better.) Thu Oct 05 1989 23:20

    The March '89 College Mathematics Journal describes an interesting
    problem in coloring the cells of rectangular grids.
    
    "Given an N x M rectangle, is it posible to color it with K colors
    such that there does NOT exist four cells of the same color that 
    form the corners of a rectangle?"
    
    They get pretty far in answering this question, eseentially solving it
    completely for K=2, and K=3.  Thus it is possible to know whether this
    can be done for any specific N x M grid for 2 or 3 colors.
    
    So for instance here is a 4 x 6 rectangle in 2 colors that satisfies
    the conditions:
    
    	+--+--+--+--+--+--+
    	|**|**|**|  |  |  |
    	+--+--+--+--+--+--+
    	|**|  |  |**|**|  |
    	+--+--+--+--+--+--+
    	|  |**|  |**|  |**|
    	+--+--+--+--+--+--+
    	|  |  |**|  |**|**|
    	+--+--+--+--+--+--+
    
    But this is known to be impossible to do for a 4 x 7 rectangle.
    
    The cover of that issue shows a 10 x 10 grid in 3 colors that satisfies
    the conditions (ie. has no "chromatic rectangles").
    
    PROBLEM:  Color a 9 X 11 grid with no chromatic rectangles.
    
    HARDER PROBLEM: Color a 9 x 12 grid with no chromatic rectangles.
    
    These ARE know to be doable, but I do not have an answer myself.  The
    authors imply that they had great difficulty finding the 10 x 10 one.

>    "Given an N x M rectangle, is it posible to color it with K colors
>    such that there does NOT exist four cells of the same color that 
>    form the corners of a rectangle?"

I suppose they want the four cells to not form the corners of an *aligned*
rectangle, since the lower right corner of your example diagram contains a
square at a 45� angle.