2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm not sure I get your definition of $D_{i,j,0}$. You're selecting a pair of squares in row $i$, and a pair of squares in row $j$ that belong to the same two columns (so $4$ squares in total)? Why is the number of good rectangles then $\sum_{i<j}D_{i,j,0}D_{i,j,1}$? $\endgroup$ – Karo Jul 10 '16 at 18:33
  • $\begingroup$ no, just two squares, such that they are in rows $i$ and $j$. But I ask they are in the same column. One square in row $i$ and the other in row $j$. $\endgroup$ – Jorge Fernández Hidalgo Jul 10 '16 at 18:33
  • $\begingroup$ ok, so for $D_{i,j,0}$ you require that the top square is black. Do you also require that the bottom square is white? $\endgroup$ – Karo Jul 10 '16 at 18:38
  • $\begingroup$ yes, sorry now is it clear why the number of good rectangles is that sum ? $\endgroup$ – Jorge Fernández Hidalgo Jul 10 '16 at 18:42
  • $\begingroup$ Yes, thanks. Why is $\sum_{i<j}D_{i,j,0}+D_{i,j,1}\leq 2n\times 2n\times 4n$? $\endgroup$ – Karo Jul 10 '16 at 18:44

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.