Two opposite cells have same color for arbitrary-sized board We color the cells a $4n\times 4n$ board ($n\geq 1$) 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 $(2n)^4$. For a coloring that puts black on the top-left $2n\times 2n$ and the bottom-right $2n\times 2n$, the number is also $(2n)^4$.
For $n=1$, $(2n)^4$ is the answer. But the argument uses case division. For arbitrary $n$ we can say that in the two examples above where the bound is achieved, each square is a corner of $(2n)^2$ different good rectangles, and if there are more than $(2n)^4$ good rectangles, some square must be in at least $(2n)^2+1$ good rectangles.
 A: Let $D_{i,j,0}$ be the number of pairs of squares in the same column in rows $i,j$ where the top square is black and bottom  square white and $D_{i,j,1}$ be the number of pairs of squares in the same column in rows $i,j$ where the top square is white and bottom square black.
The number of good rectangles is $\sum\limits_{i<j}D_{i,j,0}D_{i,j,1}$.
Notice the following two things:
for fixed $i,j$ we have $D_{i,j,0}+D_{i,j,1}\leq 4n$
$\sum\limits_{i<j}D_{i,j,0}+D_{i,j,1}\leq 2n\times2n\times 4n$
We will now maximize $\sum\limits_{i<j}D_{i,j,0}D_{i,j,1}$ subject only to those constraints and we let $D_{i,j}$ be any non-negative reals (so forget the chessboard and just think of the numbers)
Notice that if the maximum is achieved then
$D_{i,j,0}=D_{i,j,1}$ for all $i,j$
So let $D_{i,j,0}=D_{i,j,1}=A_{i,j}$
Then we must maximize $\sum\limits_{i<j}A_{i,j}^2$
subject to $\sum\limits_{i,j}A_{i,j}\leq n\times2n\times 2n$ and $A_{i,j}\leq 2n$.
Since the function $x^2$ is convex, the maximum cannot be achieved if there are two values $i<j$ and $i'<j'$ for which $0<A_{i,j},A_{i',j'}<2n$.
So the maximum is reached when we have $A_{i,j}=2n$ for $(2n)^2$ pairs and $A_{i,j}=0$ for the other $4n^2-2n$ pairs.
So the maximum is reached at $(2n)^2(2n)^2=(2n)^4$.
