An 8 x 8 chessboard is divided into p disjoint rectangles (along the lines between squares), so that each rectangle has the same number of white squares as black squares, and each rectangle has a different number of squares. Find the maximum possible value of p and all possible sets of rectangle sizes.
Solution
The requirement that the number of black and white squares be equal is equivalent to requiring that the each rectangle has an even number of squares. 2 + 4 + 6 + 8 + 10 + 12 + 14 + 16 = 72 > 64, so p < 8. There are 5 possible divisions of 64 into 7 unequal even numbers: 2 + 4 + 6 + 8 + 10 + 12 + 22; 2 + 4 + 6 + 8 + 10 + 16 + 18; 2 + 4 + 6 + 8 + 12 + 14 + 18; 2 + 4 + 6 + 10 + 12 + 14 + 16. The first is ruled out because a rectangle with 22 squares would have more than 8 squares on its longest side. The others are all possible.
2 2 2 2 2 2 2 4 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 4 2 2 2 2 2 2 2 2 1 1 1 1 1 5 5 4 1 1 1 1 1 1 5 5 1 1 1 1 1 5 5 4 1 1 1 1 1 1 5 5 1 1 1 1 1 5 5 4 1 1 1 1 1 1 5 5 1 1 1 1 1 6 6 4 3 3 3 3 3 7 6 6 3 3 3 3 3 6 6 4 3 3 3 3 3 7 6 6 3 3 3 3 3 7 7 4 4 4 4 4 4 4 4 4 2 2 2 2 2 2 2 7 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 4 2 2 2 2 2 2 2 7 1 1 1 1 1 1 4 4 2 2 2 2 2 2 2 7 1 1 1 1 1 1 4 4 3 3 3 3 3 3 6 6 3 3 3 3 3 3 4 4 3 3 3 3 3 3 6 6 3 3 3 3 3 3 6 6 4 4 4 4 4 5 5 5 5 5 5 5 5 5 6 6 4 4 4 4 4 5 5 5
Solutions are also available in: Samuel L Greitzer, International Mathematical Olympiads 1959-1977, MAA 1978, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
7 Oct 1998