Problem 4. A rectangular piece of paper $20 \times 19$, divided into unit squares, is cut into several square pieces, the cuts being made along the sides of the unit squares. A square piece of this kind is called an odd square if the length of its side is an odd number.

a) What is the minimum possible number of odd squares?

b) What is the smallest value that the sum of the perimeters of the odd squares can take?
## Solution and grading criteria:

a) If we denote by $k$ the number of square pieces obtained and by $x_{1}, x_{2}, \ldots, x_{k}$ their dimensions, then writing the area of the rectangle in two ways, we get $19 \cdot 20=x_{1}^{2}+x_{2}^{2}+\ldots+x_{k}^{2}$. Since $19 \cdot 20=380$ is divisible by 4, the square of an even number is a multiple of 4, and the square of an odd number is a number that gives a remainder of 1 when divided by 4, we deduce that the number of square pieces of odd dimension must be a multiple of 4. ...1p Note further that this number cannot be 0: the side of length 19 cannot be composed of only squares of even dimension. (Another argument: if we color the piece of paper in columns, alternately with white and black such that the first and last columns are black, we would have 20 more black squares than white ones, and a square of even dimension occupies the same number of white and black squares, so we cannot have only these.) $1 p$ An example with 4 squares of odd dimension is easy to give: for example, cutting from the last 5 columns 4 pieces $5 \times 5$ (these are the 4 squares of odd dimension). The remaining rectangular piece $20 \times 14$ can be cut into pieces $2 \times 2$. 1p

b) We color the piece of paper in columns, alternately with white and black such that the first and last columns are black. We will have 20 more black squares than white ones, and a square of even dimension occupies the same number of white and black squares. A square of odd dimension $\ell$ occupies either $\ell$ more white squares than black ones or $\ell$ more black squares than white ones. Therefore, the sum of the dimensions of the squares that cover more black squares than white ones must be 20 more than the sum of the dimensions of the squares that cover more white squares than black ones. It follows that the sum of the dimensions of the squares that cover more black squares than white ones must be at least 20, so the sum of the dimensions of the squares of odd dimension must be at least 20, thus the sum of the perimeters of the odd squares is at least 80. ........ 3p An example in which the required sum is exactly 80 is the one given in part a). .......................1p