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<\ldots <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$.
Problem
Source: IMO ShortList 1974, Bulgaria 1, IMO 1997, Day 2, Problem 1
Tags: rectangle, combinatorics, Chessboard, dissection, IMO, IMO 1974
27.12.2011 18:41
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
30.08.2016 11:22
21.12.2023 22:10
Here's an illustration of all four tilings.
Attachments:

04.01.2024 06:22
We claim that the answer is $\boxed{p = 7},$ achieved with $(a_1,a_2,a_3,a_4,a_5,a_6,a_7) = (1,2,3,4,5,8,9),(1,2,3,4,5,7,10), (1,2,3,4,6,7,9),(1,2,3,5,6,7,8).$ First note that $p \le 7$ since otherwise $2(a_1+a_2+\dots+a_p) \ge 2(1+2+\dots + 8) \ge 72 > 64,$ which is a clear contradiction. For $p = 7,$ the only possible ordered tuples $(a_1,a_2,a_3,a_4,a_5,a_6,a_7)$ such that $a_1 < a_2 < a_3 < a_4 < a_5 < a_6 < a_7$ and $a_1 + a_2 + \dots + a_7 = 32$ are $$(a_1,a_2,a_3,a_4,a_5,a_6,a_7) = (1,2,3,4,5,8,9),(1,2,3,4,5,7,10), (1,2,3,4,6,7,9),(1,2,3,5,6,7,8),(1,2,3,4,5,6,11).$$The last tuple does not have a construction since that would require us to have a rectangle of area $22$ with sidelengths less than or equal to $8,$ which is clearly impossible. The other four tuples are possible, as shown by the pictures below, proving our claim.
Attachments:

06.05.2024 11:41
$a_1 < a_2 \cdots < a_p$. We know that the i-th rectangle has $a_i$ white and $a_i$ black, or $2a_i$ squares altogether. Let $p \geq 8$ $\Rightarrow$ $a_1 \geq 1$ and $a_8 \geq 8$ $\Rightarrow$ $2(a_1 + a_2 + \cdots + a_8) \geq 2(1 + 2 + \cdots + 8) = 2.\frac{8.9}{2} = 72$ but the total number of cells in the table is 8.8 = 64, but since 72 is larger than 64, $p < 8$. We search for the largest possible p. We showed $p < 8$ $\Rightarrow$ we will prove p = 7 works, and we will find all ordered tuples $(a_1, a_2, a_3, a_4, a_5, a_6, a_7)$. We want $2(a_1 + \cdots a_7) = 64$ $\Rightarrow$ $a_1 + a_2 \cdots a_7 = 32$, where $a_1 < a_2 \cdots < a_7$ $\Rightarrow$ the ordered tuples we could get this way are $(a_1, a_2, a_3, a_4, a_5, a_6, a_7) = (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),(1,2,3,4,5,6,11)$. The last tuple doesn't work, since rectangle with area 22, can be only 2x11, but the largest side of the table is 8. The other tuples are achievable and examples are easily drawn. So the answer is p = 7, achievable with $(a_1,a_2,a_3,a_4,a_5,a_6,a_7) = (1,2,3,4,5,8,9),(1,2,3,4,5,7,10), (1,2,3,4,6,7,9),(1,2,3,5,6,7,8)$.
15.11.2024 04:34
Ban this problem. The answer is just $7$. $8$ is not possible because we need distinct even integers to sum to $64$ by area which is not possible cause $2(1+2+\dots+8) = 72 > 64$. So basically we need distinct integers $b_1, b_2, \dots b_7$ s.t. $$\sum b_i = 32$$After a check we can just find four viable pairs becuase one has $b_7=11$ which is clearly not possible. The others are possible but I don't know how to asy.
16.02.2025 04:55
The optimum is $p = 7$, attainable with $(1, 2, 3, 5, 6, 7, 8), (1, 2, 3, 4, 5, 7, 10), (1, 2, 3, 4, 5, 8, 9), (1, 2, 3, 4, 6, 7, 9)$. We easily have the bound \[ 1 + 2 + \dots + p = \dfrac{p(p + 1)}{2} \le a_1 + a_2 + \dots + a_p = 32 \implies p \le 7. \]Now we show attainability at $p = 7$, by carefully listing the possible tuples our candidates are \[ (1, 2, 3, 5, 6, 7, 8), (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). \]Clearly $(1, 2, 3, 4, 5, 6, 11)$ does not work as one of the rectangles would have a side length that is a multiple of $11$, which cannot exist as we are confined to an $8 \times 8$ grid. It is well-known that a rectangle with even area must have an equal number of white and black squares when checkerboard-colored, below are constructions:
Attachments:
