IMO 1974 · Problem 4

Consider decompositions of an \(8 \times 8\) chessboard into \(p\) non-overlapping rectangles subject to the following conditions:

(i) Each rectangle has as many white squares as black squares.

(ii) 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 value of \(p\) for which such a decomposition is possible. For this value of \(p\), determine all possible sequences \(a_1,a_2,\ldots,a_p\).

Official text of the problem. Official problem paper (PDF)

Answer

The maximum is \(\boxed{p=7}\). All possible sequences are \[ \boxed{ \begin{aligned} &(1,2,3,4,5,7,10),\\ &(1,2,3,4,5,8,9),\\ &(1,2,3,4,6,7,9),\\ &(1,2,3,5,6,7,8). \end{aligned}} \]

Solution

There are \(32\) white squares. Each rectangle contains a positive integer number of white squares, so \[ a_1+\cdots+a_p=32. \] Since the \(a_i\) are strictly increasing positive integers, \(a_i\ge i\). Hence \[ 32\ge 1+2+\cdots+p=\frac{p(p+1)}2. \] As \(1+\cdots+8=36\), we obtain \(p\le7\).

Suppose \(p=7\), and put \(b_i=a_i-i\). Then \[ 0\le b_1\le b_2\le\cdots\le b_7, \qquad b_1+\cdots+b_7=32-28=4. \] The positive terms of this nondecreasing sequence must be one of \[ (4),\quad (1,3),\quad (2,2),\quad (1,1,2),\quad (1,1,1,1). \] Indeed, these are all the partitions of \(4\). Inserting leading zeros and adding \(i\) to the \(i\)-th term gives precisely \[ \begin{aligned} &(1,2,3,4,5,6,11),\\ &(1,2,3,4,5,7,10),\\ &(1,2,3,4,5,8,9),\\ &(1,2,3,4,6,7,9),\\ &(1,2,3,5,6,7,8). \end{aligned} \]

The first sequence is impossible. Its rectangle with \(11\) white squares would also contain \(11\) black squares, giving area \(22\). The only integer side lengths for such a rectangle are \(1,22\) or \(2,11\), up to interchange; neither rectangle fits in an \(8\times8\) board.

It remains to construct decompositions for the other four sequences.

Divide each row of the board into four horizontal dominoes, each consisting of two adjacent squares. Each domino contains exactly one white and one black square. In the arrays below, each entry represents one such domino, and all dominoes with the same label form one rectangle. Thus each array represents the entire \(8\times8\) board.

For \((1,2,3,4,5,7,10)\) and \((1,2,3,4,5,8,9)\), respectively, use \[ \begin{array}{rrrr} 1&2&2&3\\ 4&4&7&3\\ 4&4&7&3\\ 10&10&7&5\\ 10&10&7&5\\ 10&10&7&5\\ 10&10&7&5\\ 10&10&7&5 \end{array} \qquad\qquad \begin{array}{rrrr} 1&2&2&3\\ 4&8&8&3\\ 4&8&8&3\\ 4&8&8&5\\ 4&8&8&5\\ 9&9&9&5\\ 9&9&9&5\\ 9&9&9&5 \end{array}. \]

For \((1,2,3,4,6,7,9)\) and \((1,2,3,5,6,7,8)\), respectively, use \[ \begin{array}{rrrr} 1&2&2&3\\ 7&4&4&3\\ 7&4&4&3\\ 7&6&6&6\\ 7&6&6&6\\ 7&9&9&9\\ 7&9&9&9\\ 7&9&9&9 \end{array} \qquad\qquad \begin{array}{rrrr} 1&2&2&3\\ 6&6&7&3\\ 6&6&7&3\\ 6&6&7&5\\ 8&8&7&5\\ 8&8&7&5\\ 8&8&7&5\\ 8&8&7&5 \end{array}. \]

In every array, the occurrences of each label \(a\) form a rectangular block containing exactly \(a\) dominoes. Consequently, the corresponding rectangle contains exactly \(a\) white and \(a\) black squares. The seven rectangles cover the board without overlap, and their white-square counts are the required distinct numbers.

Thus \(p=7\) is attainable, and exactly the four stated sequences occur.

The solution was checked against John Scholes' IMO solution archive (Kalva).