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 5 of 5: Each sequence has a board tiling

Previous step Next step

p=7\text{ is attainable for all four sequences}

Detailed analysis

Each of the four sequences is realizable by an explicit dissection into rectangles; the constructions use rectangles with areas $2a_i$ , all with both side lengths at most $8$ , and cover the board without overlap. Therefore $p=7$ is attainable, so the maximum is $7$ , and the four sequences above are exactly all possibilities.