1974 IMO Problems/Problem 4

Problem

Consider decompositions of an $8\times8$ 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.$

Solution

Since each rectangle has the same number of black squares as white squares, $a_1+a_2+\ldots +a_p=\frac{64}{2}=32$ . Clearly $a_i\ge i$ for $i=1$ to $i=p$ so $32=a_1+a_2+\ldots + a_p\ge 1+2+\ldots +p=\frac{p(p+1)}{2}$ so this forces $p\le 7$ . It is possible to decompose the board into $7$ rectangles, as we will show later. But first let us find all such sequences $a_i$ . Now $32-a_7=a_1+a_2+\ldots +a_6\ge 1+2+\ldots +6=21\implies 11\le a_7$ . For a rectangle to have $11$ white squares, it will have an area of $22$ so it's dimensions are either $1\times 22$ or $2\times 11$ - neither of which would fit on a $8\times 8$ board. So $a_7\not= 11\implies a_7\le 10$ .

If $a_7=10$ (which could fit as a $4\times 5$ rectangle) then $a_1+a_2+\ldots a_6=22$ . Then $22-a_6\ge 1+2+\ldots +5=15$ so $7\ge a_6$ . So $a_1,a_2,\ldots ,a_6$ are 6 numbers among 1-7. If $1\le k\le 7$ is the number that is not equal to any $a_i$ , then $22=a_1+a_2+\ldots +a_7=1+2+\ldots +7-k=28-k$ so $k=6$ . Then $a_1=1,a_2=2,a_3=3,a_4=4,a_5=5,a_6=7,a_7=10$ . Such a decomposition is possible. Take a $4\times 5$ rectangle on the top left corner, where there are $4$ squares horizontally and $5$ vertically. Then directly below use a $7\times 2,1\times 2$ and a $8\times 1$ rectangle to cover the 3 rows below it. It's simple from there.

Similarly, you can find the other possibilities as $\{a_1,a_2,\ldots ,a_7\}=\{1,2,3,4,5,8,9\}$ or $\{1,2,3,4,6,7,9\}$ or $\{1,2,3,5,6,7,8\}$ . Tilings are not hard to find.

The above solution was posted and copyrighted by WakeUp.

Remarks (added by pf02, October 2025)

1. The solution given above is incomplete. Expressions like "It's simple from there" and "Tilings are not hard to find" amount to hand waving rather than a proof or a solution.

2. On the discussion page https://artofproblemsolving.com/community/c6h58591 one can find the solution given above carried to its completion (by other authors), and other solutions are given, as well as pictures showing the tilings.

The original thread for this problem can be found here: [1]

1974 IMO (Problems) • Resources
Preceded by Problem 3	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 5
All IMO Problems and Solutions

Page

Toolbox

Search

1974 IMO Problems/Problem 4

Contents

Problem

Solution

Remarks (added by pf02, October 2025)

See Also