A piece of rectangular paper $20 \times 19$, divided into four units, is cut into several square pieces, the cuts being along the sides of the unit squares. Such a square piece is called 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?
Problem
Source: 2019 Romanian NMO grade VII P4
Tags: combinatorics, combinatorial geometry
rms
10.09.2024 23:47
**Problem 4.** A rectangular piece of paper \(20 \times 19\), divided into unit squares, is cut into several square-shaped pieces, with the cuts made along the sides of the unit squares. Such a square piece 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? Translated from here:
**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 obtain \( 19 \times 20 = x_1^2 + x_2^2 + \ldots + x_k^2 \).
Since \( 19 \times 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 leaves a remainder of 1 when divided by 4, we deduce that the number of square pieces with odd dimensions must be a multiple of 4.
Let's further observe that this number cannot be 0: the side with dimension 19 cannot contribute only square pieces of even dimension. (Another argument: if we color the paper alternately black and white so that the first and last columns are black, we would have 20 more black squares than white squares, but a square with an even dimension occupies as many white as black squares, so we cannot have only squares of this kind.)
An example with 4 square pieces of odd dimension is easy to give: for example, cut the last 5 columns into 4 square pieces of \( 5 \times 5 \) (these are the 4 square pieces of odd dimension). A rectangular piece of \( 20 \times 14 \) remains, which can be cut into \( 2 \times 2 \) pieces.
**b)** Let's color the paper by columns, alternately black and white so that the first and last columns are black. We will have 20 more black squares than white squares, while a square of even dimension occupies as many white as black squares. A square of odd dimension \( \ell \) occupies either \( \ell \) more white squares than black or \( \ell \) more black squares than white. Therefore, the sum of the dimensions of the squares that cover more black squares than white must be 20 more than the sum of the dimensions of the squares that cover more white squares than black. It follows that the sum of the lengths of the squares that cover more black squares than white 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 squares must be at least 80.
An example where the required sum is exactly 80 is given in a).