minimum number of congruent rectangles

Question

consider a 6*6 square which is dissected into 9 rectangles by lines parallel to its sides such that all the rectangles have integral sides.the question is - what is the minimum number of congruent rectangles?

my approach: lets start with the minimum number of non congruent rectangles and for that purpose with minimum area. if area is 1 sq.unit then there will be only 1 rectangle of 1*1

if area is 1 sq.unit then there will be only 1 rectangle of 1*1

if area is 2 sq.unit then there will be only 1 rectangle of 1*2

if area is 3 sq.unit then there will be only 1 rectangle of 1*3

if area is 4 sq.unit then there will be only 2 rectangles of 1*4 or 2*2

if area is 5 sq.unit then there will be only 1 rectangle of 1*5

if area is 6 sq.unit then there will be only 2 rectangles of 1*6 or 2*3

if area is 7 sq.unit then there will be only 1 rectangle of 1*7 but this is not possible in 6*6 square

if area is 8 sq.unit then there will be only 1 rectangle of 1*8

here we have considered all the non congruent rectangles and the summation of these areas is

1+2+3+4+4+5+6+6+8=39>36 hence we must have at least 2 congruent triangles.

so,can you check if my proof is correct? also kindly suggest an alternate solution like a geometric one if possible .

Answer 1

Let $h$ be the number of horizontal lines dissecting the area. Let $v$ be the number of vertical lines dissecting the area. The number of rectangles you wind up with is $(h+1)(v+1) = 9$. Since $0\le h\le 5, 0\le v \le 5$ and $9 = 3^2$, we have the following possibilities:

$$h+1=1, v+1=9 \Longrightarrow v=8>5 \\ h+1=9, v+1=1 \Longrightarrow h=8>5 \\ h+1=3, v+1=3 \Longrightarrow h=v=2$$

Since these are the only possible ways to achieve a product of nine with nonnegative integers no greater than $5$, it must be the last case.

Consider the position of the two vertical lines. We have the following possibilities. To the left of the first line, between the two lines, and to the right of the second line we can have areas of the following dimensions (in some order): $$1\times 6, 1\times 6, 4\times 6 \\ 1\times 6, 2\times 6, 3\times 6 \\ 2\times 2, 2\times 2, 2\times 2$$

If we add a horizontal line, the breakdown into sizes of rectangles remains constant regardless of the order of these areas. So, without loss of generality, we can look only at cases where we add lines from left to right (or top to bottom) in nondecreasing areas.

There are nine possible combinations of these area breakdowns between the vertical and horizontal lines. I am not providing an explanation, but $1\times 6, 2\times 6, 3\times 6$ for both horizontal and vertical lines yields the minimum number of congruent rectangles. This can be shown through exhaustion.

$$\begin{array}{|c|cc|ccc|}\hline a & b & b & c & c & c \\ \hline d & e & e & f & f & f \\ d & e & e & f & f & f \\ \hline g & h & h & i & i & i \\ g & h & h & i & i & i \\ g & h & h & i & i & i \\ \hline\end{array}$$

The only congruences are $b \cong d, c\cong g, f\cong h$.

You can prove that this is minimal through exhaustion (find all congruences in each of the other eight combinations of horizontal and vertical lines).

Answer 2

In this answer, I am interpreting the statement

"dissected into rectangles by lines perpendicular to its sides"

to mean that

"dissected into rectangles by line segments perpendicular to its sides"

The difference is that lines extend infinitely, so they must cut the square, while lines segments have finite length.

---

Your proof that you need at least 2 congruent rectangles is correct, and probability the best possible proof. However, to prove that 2 is indeed the minimum, you need to find a dissection with exactly 2 congruent rectangles.

Here is a hint towards that goal. The total area of the $9$ smallest rectangles which fit in this grid is $39$, as you found. In order to tile the rectangle with one duplicate, one thing you could to is remove one of those rectangles, and replace it with a smaller one. The difference between the areas of the removed and added rectangles should be exactly $3$, so you can reduce the sum of the areas from $39$ to $36$. This narrows down the possibilities somewhat.

Hint 2:

There is a valid solution where you remove the $2\times 4$ rectangle, and replace it with an extra $1\times 5$ rectangle.

Solution:

A B B B B B
A C C C C C
A D D H H I
A D D G G F
A D D G G F
A E E E E F