20. Sacha wants to cut a $6 \times 7$ rectangle into squares that all have integer length sides. What is the smallest number of squares he could obtain?
A 4
B 5
C 7
D 9
E 42
Solution
B
The largest single square with integer length sides that can be cut from a $6 \times 7$ rectangle is a $6 \times 6$ square. This would leave a $6 \times 1$ strip to be cut into squares, which would require six $1 \times 1$ squares, meaning the rectangle is cut into seven squares. Next consider the case when the largest square cut out is a $5 \times 5$ square. The remaining region to be cut up would consist of a $5 \times 1$ strip, made up of five $1 \times 1$ squares and either two $6 \times 1$ strips made up of twelve $1 \times 1$ squares or one $6 \times 2$ strip which could be cut into three $2 \times 2$ squares. In each case, more than seven squares would be created.
Now consider the case where the largest square is a $4 \times 4$ square. It is possible to cut out this square to leave a $4 \times 2$ strip, which could be further cut into two $2 \times 2$ squares and a $3 \times 6$ strip, which could be further cut into two $3 \times 3$ squares, making five squares in total, as shown in the diagram. In the case where the largest square is a $3 \times 3$ square, since the total area of the original rectangle is 42 square units and $42=4 \times(3 \times 3)+6$, the rectangle could not be cut into fewer than 5 squares. Similarly, if the largest squares are $2 \times 2$, then since $42=10 \times(2 \times 2)+2$, more than 10 squares are required and if the largest square is a $1 \times 1$ square, at least 42 squares would be needed.. Hence, the smallest number of squares that Sacha could obtain is 5 .