The November 15, 2006 PoW (Problem of the Week)*

A rectangle has dimensions 39.375 inches by 136.5 inches.

Find the least number of squares that will fill the rectangle.

Also, find the least number of squares that will fill the rectangle, if every square must be the same size. (Equivalently, find the largest square that can be tiled to completely fill the rectangle.)

We solve the second question first:

We convert each number to a fraction and get a common denominator, then find the gcd (greatest common divisor) of the numerators. That is, with side lengths 39.375" and 136.5", we convert those numbers to fractions (with a common denominator):

39.375 = 315/8 136.5 = 273/2 = 1092/8

Now we need to find the largest common factor of 315 and 1092. Since 315 = 3x3x5x7 and 1092 = 2x2x3x7x13, the greatest common divisor of 315 and 1092 is 3×7 = 21. So 21/8 =2.625 is the largest number that divides evenly into the two numbers 39.375 and 136.5. There will be (1092/21)×(315/21)= (136.5/2.625)×(39.375/2.625) = 52×15 = 780 squares, each one a 2-5/8" x 2-5/8" ( or 2.625" x 2.625") square needed to fill the rectangle (52 in each row,with 15 rows).

Shavetambry Tejpal sent in a solution that I summarize below:

length of the rectangle = 136.5 breadth of the rectangle = 39.375

Firstly I will solve the second part. Since we want least number of squares to fill the rectangle therefore 'a' should be the greatest possible number to divide 136.5 and 39.375, i.e. a should be the greatest common divisor (gcd) of 136.5 and 39.375. Now we will find gcd.

136.5 = 3 * 39.375 + 18.375

39.375 = 2 * 18.375 + 2.625

18.375 = 7 * 2.625 + 0

This implies that gcd(39.375, 136.5) = 2.625. Thus side of each square is 2.625.

39.375 / 2.625 = 15 and 136.5 / 2.625 = 52. Thus least number of squares that can fill given rectangle is 52 * 15 = 780.

Now I will solve the first part. Number of squares lengthwise is 52 and breadthwise is 15. Now we will combine these squares in order to find least number of squares to fill the rectangle. First three squares would be of dimension 15 by 15. In this way length of 45 units is utilized. Now the rectangle which is left with us excluding three squares is 7 by 15. Again in the same way we can make two squares of dimension 7 by 7. In this way breadth of 14 units is utilized.

Now we are left with the rectangle of dimension 7 by 1. These can further be subdivided into seven squares each of dimension 1 by 1. In this way the least number of squares to fill the rectangle is 3 + 2+ 7 = 12. The required answer is 12.

Note that the three numbers 3, 2, and 7 are involved in the Euclidean algorithm for finding the gcd!