An $8 \times 8$ checkerboard has alternating black and white squares. How many distinct rectangles, with sides on the grid lines of the checkerboard and containing at least $4$ black squares, can be drawn on the checkerboard?
I ended up getting$$3(2) + 5(2)(2) + (6(2)(2) - 2) + (5(2)(2) - 2) + (4(2)(2) - 2) + (3(2)(2) - 2) + (2(2)(2) - 2) + 1 = 97.$$ Is this correct?
EDIT: By distinct I mean not identical -- for example a $1 \times 4$ rectangle that begins with a black square would be considered the same as another $1 \times 4$ rectangle that begins with a black square, and those would be different from both (1) a $1 \times 4$ rectangle that begins with a white square and (2) a $4 \times 1$ rectangle.
$\endgroup$ 53 Answers
$\begingroup$For rectangles, if there exists an $a\times b$ rectangle with $a\neq b$ such that it contains at least four black squares, then its transpose $b\times a$ will certainly be a distinct rectangle with at least four black squares that will fit on the chessboard. Similarly, any rectangle such that its transpose is a distinct rectangle will have the property that reversing the colors within the rectangle is possible by shifting it (for example, the only two $7\times 8$ rectangles on the board are both distinct, as one has a white square in the upper left corner while the other has a black square in the upper left corner). Thus for any $a\times b$ rectangle that has at least four white squares, reversing the colors (by shifting one row up or down as needed) will contain at least four black squares. This is true for any $a\times b$ rectangle that possesses at least four black squares except $1\times 7$ rectangles. A $1\times 7$ rectangle that possesses four black squares only contains three white squares.
Next, let's consider squares. The smallest $a\times a$ square that contains at least four black squares is the $3\times 3$ square. This contains either 5 black and 4 white or 4 black and 5 white. Its transpose will be nondistinct. But, shifting it one row or column will reverse the colors and be distinct. Thus, each such square will have a second "copy" except for the $8\times 8$ square because it cannot be shifted any rows or columns to reverse the colors.
This yields:
$1\times 7, 7\times 1$: 2 distinct, count each once
$1\times 8, 2\times 4^+, 3\times 4^+, 4\times 5^+, 5\times 6^+, 6\times 7^+, 7\times 8$: 21, count each four times.
$3\times 3, 4\times 4, 5\times 5, 6\times 6,7\times 7$: 5, count each twice.
$8\times 8$: Count once.
For this count, I am using $2\times 4^+$ to represent all distinct pairs where the second number is at least 4, thus $2\times 4, 2\times 5, 2\times 6, 2\times 7, 2\times 8$ are all represented by this shorthand.
This yields $2+21\cdot 4+5\cdot 2+1 = 97$, which is the answer you arrived at.
$\endgroup$ $\begingroup$For the interpretation by @bof, let $$S = \left\{r_1\in\{1,\dots,8\},r_2\in\{r_1,\dots,8\},c_1\in\{1,\dots,8\},c_2\in\{c_1,\dots,8\}:\\ \sum_{r=r_1}^{r_2}\sum_{c=c_1}^{c_2} \mod(r+c,2) \ge 4\right\}.$$Then $|S|= 683$, but some of these are translations of each other, and the OP wants to count only the equivalence classes.
$\endgroup$ 1 $\begingroup$2x2 squares have 4 black squares
all 3x3 squares have at least 4 black squares, as do all 4x4, 5x5, 6x6, 7x7, and 8x8 squares.
there are 6x6=36 3x3 squares
there are 5x5=25 4x4 squares
there are 4x4=16 5x5 squares
there are 3x3=9 6x6 squares
there are 2x2=4 7x7 squares
there is 1 8x8 square
Summing we get 91 squares (not my own answer, got it from )
$\endgroup$ 1
