Solution to Problem #8

For two colors, 2 x N is allowable for any N.  Just paint the top row
black and the bottom row white.

There is a common thread running through all the other solutions.  In
each column, there will be some number of pairs of cells that have the
same color.  We cannot duplicate any of those pairs in that color in
another column.  For example, if the first column of a 4 by N rectangle
is WBBW, no other column can have the first and fourth rows white, and
no other column can have the second and third rows black.  In a 4 by N
rectangle there are C(4,2)=six pairs of rows.  Each pair can have one
column where both cells are black and one column where both cells are
white.  This makes a total of twelve color-pairs.  In each column, if
there are two cells of one color and two of the other, there will be two
color-pairs.  So there are a maximum of six columns.  We can display an
example with six columns:

WWWBBB
WBBBWW
BWBWBW
BBWWWB


The largest 3 high is 6 wide.  To prove existence, take any three rows
of the 4 x 6 (above).  To prove that it cannot be wider, each column
must have two cells of one color and one of the other, using up one
color-pair.  There are 2*C(3,2)=6 color pairs, so there is a maximum of
six columns.


For 5 high we can only have 4 wide.  For existence, delete one column
from the above 4 x 6 and rotate.  There are ten pairs of rows.  Each
column, with 3 of one color and 2 of the other uses four color-pairs. 
So with four columns we have used eight pairs of each color and a fifth
column
would make eleven pairs of that color.

For 6 high we can have 4 wide, rotating the 4x6.

For greater than 6 high we can only have two wide.

For more colors, we should distribute the rows as evenly as possible
between the colors and count pairs as above.  This wil give an upper
bound which seems like it should be achievable, but I cannot prove it.
The frightening case is 5 high with two colors where we require that all
columns have three white and two black squares.  There are ten allowable
white pairs so we should be able to have three columns.  But we cannot.