IMO 1974 SL 11

Problem

II 5 (BUL 1)IMO4 Consider a partition of an 8 \times 8 chessboard into p rectangles whose interiors are disjoint such that each of them has an equal number of white and black cells. Assume that a1 < a2 < \cdot \cdot \cdot < ap, where ai denotes the number of white cells in the ith rectangle. Find the maximal p for which such a partition is possible and for that p determine all possible corresponding sequences a1, a2, . . . , ap.

Solution

First, we notice that a1 + a2 + \cdot \cdot \cdot + ap = 32. The numbers ai are distinct, and consequently ai \geqi and a1 + \cdot \cdot \cdot + ap \geqp(p + 1)/2. Therefore p \leq7. The number 32 can be represented as a sum of 7 mutually distinct positive integers in the following ways: (1) 32 = 1 + 2 + 3 + 4 + 5 + 6 + 11; (2) 32 = 1 + 2 + 3 + 4 + 5 + 7 + 10; (3) 32 = 1 + 2 + 3 + 4 + 5 + 8 + 9; (4) 32 = 1 + 2 + 3 + 4 + 6 + 7 + 9; (5) 32 = 1 + 2 + 3 + 5 + 6 + 7 + 8. The case (1) is eliminated because there is no rectangle with 22 cells on an 8 \times 8 chessboard. In the other cases the partitions are realized as below. 8 16 14 16 Case (2) Case (3) Case (4) Case (5)