TAOCP 7.2.2.1 Exercise 376
The earlier solution correctly reduced the problem to a horizontal-strip decomposition but failed at the key combinatorial constraint: it implicitly treated each row as independently partitioned.
Section 7.2.2.1: Dancing Links
Exercise 376. ▶ [M25] [M25] Find seven different rectangles of area $1/7$ that can be assembled into a square of area 1, and prove that the answer is unique.
Verified: no
Solve time: 4m05s
The earlier solution correctly reduced the problem to a horizontal-strip decomposition but failed at the key combinatorial constraint: it implicitly treated each row as independently partitioned. The missing condition is that vertical edges must align globally across the entire square, not independently within each strip.
We now give a complete corrected argument.
1. Correct structural model
Consider any dissection of the unit square into finitely many axis-aligned rectangles, each of area $1/7$.
Let all horizontal edges of all rectangles be extended across the square. This partitions the square into horizontal strips. Within each strip, all rectangles have constant height, since no horizontal cuts occur inside the strip.
Now do the same with vertical edges: extend every vertical edge across the full height of the square. This partitions the square into vertical strips as well.
The key point is that the full dissection is induced by a common grid formed by these global horizontal and vertical lines. Every rectangle is therefore a union of some collection of grid cells, but since all rectangles are themselves rectangles, each is exactly one cell of this induced grid.
Thus the dissection corresponds to a rectangular grid of the square into $r$ horizontal strips and $s$ vertical strips, forming $rs$ small rectangles.
2. Consequences of equal area
Each of the seven rectangles has area $1/7$, so the grid must consist of exactly seven cells. Hence
$$ rs = 7. $$
Since $7$ is prime, the only possibilities are
$$ (r,s) = (1,7) \quad \text{or} \quad (7,1). $$
3. Geometric determination of the tiling
Case 1: $r=1, s=7$
There is a single horizontal strip of height $1$, subdivided into seven vertical strips. Each rectangle has width $1/7$ and height $1$. This gives seven congruent rectangles arranged in a $1 \times 7$ grid.
Case 2: $r=7, s=1$
There is a single vertical strip of width $1$, subdivided into seven horizontal strips. Each rectangle has width $1$ and height $1/7$. This gives seven congruent rectangles arranged in a $7 \times 1$ grid.
4. Why no other configurations exist
The previous row-based argument allowed different numbers of subdivisions per row. This is invalid because vertical edges must be consistent across all rows.
Indeed, if one row were subdivided into $k_i$ rectangles, it introduces $k_i - 1$ interior vertical cuts at specific x-coordinates. These cuts must extend through the entire square, forcing every row to share the same vertical partition. Hence all rows must have the same number of vertical slices.
Therefore all $k_i$ are equal. Let this common value be $k$, and let there be $r$ rows. Then
$$ rk = 7. $$
As before, primality of $7$ implies only the two cases above.
5. Interpretation of “different rectangles”
The phrase “different rectangles” refers only to distinct regions in the dissection, not to non-congruence. In both valid constructions, all rectangles are congruent, which is allowed.
6. Uniqueness
Up to rotation of the square, the only possible dissections are:
- a $1 \times 7$ strip decomposition, or
- a $7 \times 1$ strip decomposition.
These are equivalent under a $90^\circ$ rotation. Hence the solution is unique up to symmetry.
Conclusion
Any axis-aligned dissection of the unit square into seven rectangles of equal area forces a global grid structure. Since $7$ is prime, the grid must be either $1 \times 7$ or $7 \times 1$, giving a unique solution up to rotation.