MathLabs

Problem 4

Consider decompositions of an 8×88\times8 chessboard into pp non-overlapping rectangles. Each rectangle has as many white squares as black squares. If aia_i is the number of white squares in the ii-th rectangle, then a1<a2<⋯<apa_1<a_2<\cdots<a_p. Find the maximum possible pp, and for this pp determine all possible sequences a1,…,apa_1,\ldots,a_p.
Step 2 of 5: The maximum is at most 77
Previous stepNext step
p(p+1)2≤32  ⟹  p≤7\frac{p(p+1)}2\le32\implies p\le7
Detailed analysis

For p=8p=8, the lower bound gives 1+⋯+8=36>321+\cdots+8=36>32, impossible. Therefore p≤7p\le7. It remains to show that seven rectangles can in fact be realized and to determine their possible sequences.