IMO 1974 Problem 4
The quantity attached to a rectangle is not its area but half its area, because a rectangle containing equally many white and black squares has even area and the number of white squares equals the num…
Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 10m53s
Problem
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, \cdots, a_p$.
Exploration
The quantity attached to a rectangle is not its area but half its area, because a rectangle containing equally many white and black squares has even area and the number of white squares equals the number of black squares. Since the whole board contains $32$ white squares, the numbers $a_1,\dots,a_p$ are distinct positive integers whose sum is $32$.
A first attempt is to ignore geometry and maximize the number of distinct positive integers summing to $32$. The smallest possible sum of $p$ distinct positive integers is
$$1+2+\cdots+p=\frac{p(p+1)}2.$$
This gives $\frac{7\cdot 8}{2}=28\le 32$ and $\frac{8\cdot 9}{2}=36>32$, so purely arithmetically one could hope for $p=7$.
For $p=7$, the largest entry must be at least
$$32-(1+2+3+4+5+6)=11,$$
and because the total sum is exactly $32$, the only possible sequence is
$$1,2,3,4,5,6,11.$$
The corresponding largest rectangle would have area $22$. Such a rectangle cannot exist in an $8\times8$ board because $22=2\cdot11$ and one side would have length $11$. This suggests that $p=7$ is impossible.
For $p=6$, the smallest five distinct positive integers sum to $15$. Hence
$$a_6\le 32-15=17.$$
The value $17$ would correspond to a rectangle of area $34$, and no rectangle of area $34$ fits into an $8\times8$ board because $34=2\cdot17$. Thus $a_6\le16$.
To make $a_6=16$, the remaining five numbers must sum to $16$. The smallest possible sum of five distinct positive integers is $15$, so the only possibility is
$$1,2,3,4,6,16.$$
The remaining task is to construct a decomposition realizing these values.
The potentially dangerous step is the deduction that a rectangle with equal numbers of white and black squares must have area $2a_i$. That statement is correct because the numbers of white and black squares are equal by hypothesis, so each equals $a_i$.
Problem Understanding
We must partition an $8\times8$ chessboard into non-overlapping axis-parallel rectangles. Every rectangle must contain the same number of white and black squares. If $a_i$ denotes the number of white squares in the $i$-th rectangle, then the numbers $a_1,\dots,a_p$ must be strictly increasing.
This is a Type A problem. We must determine the maximum possible value of $p$ and then determine all sequences
$$a_1<a_2<\cdots<a_p$$
that can occur when this maximum value is attained.
The arithmetic condition gives
$$a_1+\cdots+a_p=32,$$
since the whole board contains $32$ white squares. Maximizing the number of distinct positive integers with fixed sum suggests $p$ might be $7$, but geometric restrictions on the sizes of rectangles prevent this. The key difficulty is combining the arithmetic constraint on the numbers $a_i$ with the geometric restriction that every rectangle must fit inside an $8\times8$ board.
The answer will be
$$p_{\max}=6,$$
and for this value the only possible sequence is
$$1,2,3,4,6,16.$$
The reason is that a hypothetical seventh rectangle would force the existence of a rectangle of area $22$, which cannot fit inside the board, while for six rectangles the arithmetic constraints force a unique sequence, and that sequence can actually be realized.
Proof Architecture
The proof will use the following claims.
Lemma 1. For every rectangle in the decomposition, its area equals $2a_i$.
Sketch. The rectangle contains $a_i$ white squares and, by hypothesis, also $a_i$ black squares.
Lemma 2. The numbers $a_1,\dots,a_p$ satisfy
$$a_1+\cdots+a_p=32.$$
Sketch. The board contains exactly $32$ white squares.
Lemma 3. The value $p=7$ is impossible.
Sketch. Distinctness forces the sequence to be $1,2,3,4,5,6,11$, hence a rectangle of area $22$ must occur, but no rectangle of area $22$ fits inside an $8\times8$ board.
Lemma 4. If $p=6$, then necessarily
$$(a_1,\dots,a_6)=(1,2,3,4,6,16).$$
Sketch. The largest value cannot be $17$ because that would require a rectangle of area $34$. Hence $a_6\le16$. Since the first five distinct positive integers sum to at least $15$, equality must occur.
Lemma 5. The sequence
$$1,2,3,4,6,16$$
is realizable.
Sketch. Give an explicit partition of the board into rectangles of areas $2,4,6,8,12,32$.
The hardest direction is proving that no other sequence can occur when $p=6$. The most delicate point is converting the geometric restriction on rectangle dimensions into the bounds $a_6\neq17$ and $11$ being impossible for $p=7$.
Solution
We first establish two basic facts.
Lemma 1
For every rectangle in the decomposition, its area equals $2a_i$.
Proof
By definition, the $i$-th rectangle contains $a_i$ white squares. Condition (i) states that it contains equally many black squares. Hence it contains exactly $a_i$ black squares.
Therefore the total number of squares in the rectangle is
$$a_i+a_i=2a_i.$$
Thus its area equals $2a_i$. ∎
Certification. This identifies the exact area of each rectangle; replacing it merely by the weaker statement that the area is even would lose the numerical information needed later.
Lemma 2
The numbers $a_1,\dots,a_p$ satisfy
$$a_1+\cdots+a_p=32.$$
Proof
An $8\times8$ chessboard contains $64$ squares, exactly half of which are white. Hence the board contains $32$ white squares.
The rectangles form a partition of the board, so the total number of white squares in all rectangles is
$$a_1+\cdots+a_p.$$
This must equal the total number of white squares on the board, namely $32$. Therefore
$$a_1+\cdots+a_p=32.$$
∎
Certification. This converts the geometric problem into an arithmetic problem on distinct positive integers summing to $32$; ignoring this identity would make it impossible to bound $p$.
Lemma 3
The value $p=7$ is impossible.
Proof
Since
$$a_1<a_2<\cdots<a_7$$
are distinct positive integers, we have
$$a_1+a_2+\cdots+a_7 \ge 1+2+3+4+5+6+7 =28.$$
By Lemma 2, the sum equals $32$, so the excess over the minimum possible sum is $4$.
To keep seven distinct increasing positive integers and increase the total sum by only $4$, the only possibility is
$$(a_1,\dots,a_7)=(1,2,3,4,5,6,11).$$
Indeed, the first six entries must be the smallest possible values $1,2,3,4,5,6$, whose sum is $21$, and then
$$a_7=32-21=11.$$
By Lemma 1, the corresponding rectangle has area
$$2a_7=22.$$
A rectangle of area $22$ has side lengths $(1,22)$ or $(2,11)$ up to order. Neither fits inside an $8\times8$ board because one side exceeds $8$.
This contradiction shows that $p=7$ is impossible. ∎
Certification. This proves the crucial upper bound; stopping at the inequality $p\le7$ would not determine the maximum.
Since $p=7$ is impossible and
$$1+2+3+4+5+6=21\le32,$$
it follows that
$$p\le6.$$
Lemma 4
If $p=6$, then necessarily
$$(a_1,\dots,a_6)=(1,2,3,4,6,16).$$
Proof
Assume $p=6$.
Since the first five entries are distinct positive integers,
$$a_1+a_2+a_3+a_4+a_5 \ge 1+2+3+4+5 =15.$$
Using Lemma 2,
$$a_6 =32-(a_1+\cdots+a_5) \le 17.$$
Suppose first that $a_6=17$. By Lemma 1, the corresponding rectangle has area
$$2a_6=34.$$
A rectangle of area $34$ has side lengths $(1,34)$ or $(2,17)$ up to order. Such a rectangle cannot fit inside an $8\times8$ board. Hence
$$a_6\neq17.$$
Therefore
$$a_6\le16.$$
Again using Lemma 2,
$$a_1+\cdots+a_5 =32-a_6 \ge16.$$
Since the minimum possible value of the left-hand side is $15$, equality $a_6=16$ forces
$$a_1+\cdots+a_5=16.$$
The only five distinct positive integers whose sum is $16$ are
$$1,2,3,4,6.$$
Consequently
$$(a_1,\dots,a_6)=(1,2,3,4,6,16).$$
∎
Certification. This establishes uniqueness of the sequence for the maximal value of $p$; merely showing that one sequence works would not solve the classification part of the problem.
Lemma 5
The sequence
$$1,2,3,4,6,16$$
is realizable.
Proof
Divide the board as follows.
Take the leftmost four columns as one rectangle. Its dimensions are $4\times8$, so its area is
$$32,$$
and therefore it contributes
$$a=16.$$
In the remaining $4\times8$ rectangle, partition the rows from top to bottom into pieces of heights $3,2,2,1$.
The top strip has dimensions $4\times3$, area $12$, and contributes $a=6$.
The next strip has dimensions $4\times2$. Divide it into a $3\times2$ rectangle of area $6$ and a $1\times2$ rectangle of area $2$. These contribute $a=3$ and $a=1$.
The next strip has dimensions $4\times2$, area $8$, and contributes $a=4$.
The bottom strip has dimensions $4\times1$, area $4$, and contributes $a=2$.
Thus the six rectangles have areas
$$2,\ 4,\ 6,\ 8,\ 12,\ 32.$$
By Lemma 1, their corresponding values of $a$ are
$$1,\ 2,\ 3,\ 4,\ 6,\ 16.$$
Every listed area is even, so each rectangle contains equally many white and black squares. Hence all conditions are satisfied.
Therefore a decomposition with sequence
$$1,2,3,4,6,16$$
exists. ∎
Certification. This proves existence; without an explicit construction the preceding lemmas would provide only an upper bound.
Combining Lemmas 3, 4, and 5, the maximum number of rectangles is
$$p=6,$$
and for this value the only possible sequence is
$$1,2,3,4,6,16.$$
$$\boxed{p_{\max}=6,\qquad (a_1,a_2,a_3,a_4,a_5,a_6)=(1,2,3,4,6,16).}$$
Verification of Key Steps
The first delicate step is the proof that $p=7$ is impossible. Starting from seven distinct positive integers summing to $32$, the minimum possible sum is $28$. The deficit from $32$ is only $4$. Hence the first six terms must remain $1,2,3,4,5,6$, and the last term becomes $11$. This yields a rectangle of area $22$. The only factorizations of $22$ are $1\cdot22$ and $2\cdot11$, both incompatible with an $8\times8$ board. A careless argument might claim merely that area $22$ is “too large”, which is false because areas larger than $22$ certainly fit inside the board.
The second delicate step is excluding $a_6=17$ when $p=6$. The issue is not that area $34$ exceeds some global area bound. The board has area $64$, so that reasoning would fail. The correct argument uses dimensions: area $34$ forces side lengths $(1,34)$ or $(2,17)$, and one side necessarily exceeds $8$.
The third delicate step is proving uniqueness of the sequence for $p=6$. Once $a_6\le16$, the remaining five numbers sum to at least $16$. Since five distinct positive integers have sum at least $15$, equality must occur. The only way to increase the minimum sum $15$ by exactly $1$ while preserving distinctness is to replace $5$ by $6$, giving $1,2,3,4,6$. Missing this arithmetic rigidity would leave many apparent candidates.
Alternative Approaches
A different route begins with areas rather than the numbers $a_i$. Let the rectangle areas be
$$2a_1<2a_2<\cdots<2a_p.$$
These are distinct even positive integers summing to $64$. The smallest possible sum of seven distinct even positive integers is
$$2+4+6+8+10+12+14=56.$$
The remaining $8$ units of area force the largest area to be $22$, producing the same contradiction as above. This immediately gives $p\le6$.
For $p=6$, the areas must sum to $64$. The smallest possible sum of six distinct even positive integers is
$$2+4+6+8+10+12=42.$$
The remaining $22$ units must be added while respecting the dimensional restriction that no rectangle may have area $34$. This again forces the largest area to be $32$ and leads to the unique area sequence
$$2,4,6,8,12,32,$$
hence to
$$1,2,3,4,6,16.$$
The main proof is preferable because it works directly with the quantities $a_i$ appearing in the statement and separates the arithmetic and geometric constraints cleanly.