[Math] Two opposite cells have same color

combinatorics

We color the cells a $4\times 4$ board in black and white. What is the maximum number of "rectangles", i.e. four cells that together form a rectangle with sides parallel to the sides of the board, such that the two cells in the opposite corner have one color and the other two cells have the other color?

For a chessboard coloring, the number is $2^4=16$. For a coloring that puts black on the top-left $2\times 2$ and the bottom-right $2\times 2$, the number is also $16$.

Best Answer

(Opening lines stolen from Henning Makholm) In the two colorings you give, each square is the corner of 4 different good rectangles. Clearly if there is a solution with more than 16 good rectangles, then there needs to be at least one square that is in at least 5 good rectangles.

By appropriate permutations of rows and columns (all of which preserve the good rectangles), we can arrange it such that this square is in the lower left corner -- a1 in chess notation. Without loss of generality we can assume it is black:

4  ? * * *
3  ? * * *
2  ? * * *
1  B ? ? ?
   a b c d

To be part of at least five rectangles, a1 must have three whites in one direction, which might as well be the 1 row, and at least two whites in the other. Then five of the opposite corners must be black, including at least two in the same column. 

4  ? * * *
3  W B * *
2  W B B *
1  B W W W
   a b c d

If a4 is black we must have c3 and d2 black to give five rectangles from a1 

4  B * * *
3  W B B *
2  W B B B
1  B W W W
   a b c d

We do best to fill it in like this

4  B W W W
3  W B B B
2  W B B B
1  B W W W
   a b c d

which only gives 12.

If a4 is white we can get as many as nine rectangles including a1 if we fill the rest with black, but that is all we get. We can get our five for a1 like this 

4  W B * *
3  W B * *
2  W B B B
1  B W W W
   a b c d

but the best we can do is nine 

4  W B B B
3  W B B B
2  W B B B
1  B W W W
   a b c d

or we have to have five blacks in rows 2 and 3

4  W * * *
3  W B B *
2  W B B B
1  B W W W
   a b c d

and more whites in the stars won't help us. 16 is the best

Related Question