Problem 4

Consider decompositions of an

8\times8

chessboard into

p

non-overlapping rectangles. Each rectangle has as many white squares as black squares. If

a_i

is the number of white squares in the

i

-th rectangle, then

a_1<a_2<\cdots<a_p

. Find the maximum possible

p

, and for this

p

determine all possible sequences

a_1,\ldots,a_p

Step 1 of 5: Count the white squares

Previous step Next step

a_1+\cdots+a_p=32,\qquad 32\ge1+2+\cdots+p=\frac{p(p+1)}2

Detailed analysis

The whole board has $32$ white squares. Since rectangle $i$ has $a_i$ white squares and the rectangles partition the board, $a_1+\cdots+a_p=32$ . The strict inequalities and positivity imply $a_i\ge i$ , so $32\ge1+2+\cdots+p=p(p+1)/2$ .