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 4 of 5: Enumerate the four possible sequences

Previous step Next step

a_7=10\Rightarrow(a_1,\ldots,a_7)=(1,2,3,4,5,7,10)

Detailed analysis

Enumerating strictly increasing positive integer 7-tuples summing to $32$ with $a_7\le10$ gives exactly the four sets $\{1,2,3,4,5,7,10\}$ , $\{1,2,3,4,5,8,9\}$ , $\{1,2,3,4,6,7,9\}$ , and $\{1,2,3,5,6,7,8\}$ . For example, if $a_7=10$ , the first six sum to $22$ ; they must be six of $1,\ldots,7$ , so the omitted value is $6$ , yielding $(1,2,3,4,5,7,10)$ . The other values follow identically by distributing the excess over the minimal sequence.