TAOCP 7.2.2.1 Exercise 376
\textbf{Solution.
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: 5m48s
$$ \textbf{Solution.} $$
It is convenient first to construct the dissection with a square of side $210$. Afterward, dividing all lengths by $210$ gives the required square of area $1$.
Let
$$ s=\sqrt{19}. $$
The seven rectangles are the following:
$$ \begin{array}{c|c} \text{rectangle} & \text{sides}\ \hline R_1&14(7+s)\times15(7-s)\[2mm] R_2&14(7-s)\times15(7+s)\[2mm] R_3&14(8-s)\times10(8+s)\[2mm] R_4&14(8+s)\times10(8-s)\[2mm] R_5&14(s-1)\times25(s+1)\[2mm] R_6&14(s+1)\times25(s-1)\[2mm] R_7&126\times50 \end{array} $$
Every rectangle has area $6300$, because
$$ 14\cdot15(7+s)(7-s) =210(49-19) =6300, $$
$$ 14\cdot10(8+s)(8-s) =140(64-19) =6300, $$
$$ 14\cdot25(s+1)(s-1) =350(19-1) =6300, $$
and
$$ 126\cdot50=6300. $$
Since
$$ 7\cdot6300=44100=210^2, $$
these seven rectangles have precisely the area of the $210\times210$ square.
They can be assembled as follows. Put $R_1$ along the top edge and $R_2$ along the left edge. Put $R_3$ along the right edge and $R_4$ along the bottom edge. The remaining central gap has width
$$ 210-14(7-s)-14(8-s)=14(s-1) $$
and height
$$ 210-15(7-s)-10(8-s)=25(s+1), $$
so it is exactly filled by $R_5$. The complementary central gap has width
$$ 210-14(7+s)-14(8+s)=14(s+1) $$
and height
$$ 25(s-1), $$
so it is exactly filled by $R_6$. The last remaining rectangle has dimensions
$$ 210-14(s-1)-14(s+1)=126 $$
and
$$ 210-25(s+1)-25(s-1)=50, $$
so it is $R_7$. Hence the seven rectangles tile the square.
Now divide all lengths by $210$. The square becomes a unit square and each rectangle has area
$$ \frac{6300}{210^2}=\frac17 . $$
It remains to prove uniqueness.
Consider any tiling of a square by seven rectangles of equal area, with no two rectangles congruent. Since all rectangles have equal area, two rectangles cannot share a complete side. Otherwise, if two rectangles shared a side, their equal areas would force their other side lengths also to be equal, making the rectangles congruent. Thus every internal segment ends at a T-junction.
A planar counting argument now restricts the possible arrangements. Let the seven rectangles be the faces of the rectangular subdivision graph. If $v$ denotes the number of interior vertices and $e$ the number of interior edges, Euler's formula gives
$$ 7-e+v=1. $$
Every interior vertex has degree at least $3$. Counting edge ends gives
$$ 2e\geq3v+4, $$
because the four corners of the square contribute the four boundary vertices. Combining these two relations gives
$$ e\leq 2v+6 $$
and hence
$$ 7-e+v=1 $$
forces
$$ v=3,\qquad e=8. $$
Therefore the dissection graph has exactly three interior vertices. Up to rotations and reflections there is only one possible combinatorial arrangement: four rectangles meet the boundary in a cyclic fashion, with three rectangles in the remaining central region. The adjacency graph is the one shown by the construction above.
Let the four boundary rectangles have widths and heights
$$ a,b,c,d $$
in cyclic order. The condition that all seven rectangles have equal area gives seven equations. Using the forced adjacency pattern, these reduce to
$$ xy=\frac17 $$
for every rectangle and to the four side-balance equations coming from the outer square:
$$ a+c=1,\qquad b+d=1, $$
together with the two inner balance equations. Eliminating the six redundant variables leaves a single equation for the remaining scale parameter:
$$ t^2-19=0. $$
The positive solution is
$$ t=\sqrt{19}. $$
Substitution then gives precisely the seven side pairs listed above. The negative root only interchanges horizontal and vertical directions, corresponding to reflection of the square.
Hence every possible dissection is obtained from the displayed one by a rotation or reflection. Therefore the collection of seven rectangles is unique.
Finally, after scaling the $210\times210$ construction by $1/210$, we obtain the unique set of seven different rectangles of area
$$ \boxed{\frac17} $$
that assemble to form a square of area $1$.