3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ By 'rectangles', you mean 2*2 squares? $\endgroup$ – Sawarnik Jul 9 '16 at 20:49
  • 2
    $\begingroup$ @Sawarnik: Not necessarily. One of the rectangles is the top $2 \times 4$ part of the board. In the chessboard coloring, opposite corners of the rectangle have the same color and neighboring corners have different corners. One of the successful rectangles in the block coloring in the last paragraph is the top three rows. $\endgroup$ – Ross Millikan Jul 9 '16 at 21:00
  • $\begingroup$ I was hoping for a simpler answer. The number of pairs of cells in one row that can participate in rectangles is the product of the number of whites and the number of blacks. Once we see that asking for more than $16$ rectangles requires a row with three of the same color, it seems like it should be easy to show this leads to fewer rectangles, but I couldn't get there. $\endgroup$ – Ross Millikan Jul 12 '16 at 2:09
  • $\begingroup$ @RossMillikan A simpler answer was given that works for any $2n\times 2n$ board: math.stackexchange.com/questions/1855185/… $\endgroup$ – Karo Jul 12 '16 at 7:02
1
$\begingroup$

(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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.