Browse · MathNet
PrintXXIV OBM
Brazil geometry
Problem
A finite collection of squares has total area . Show that they can be arranged to cover a square of side .
Solution
Let the sides of the squares be equal to for ( is the number of squares).
If some then the th square will cover the unit square. Now let's assume the case when for all .
Every number must satisfy for some integer . Now let's decrease every th square to the square with side . Then its area would decrease by at most times. Therefore the area of all squares will be greater than .
Now let's prove we can tile the unit square fully with the new squares. Let's divide the unit square into squares of side . First place the squares with side , if they exist. Then on the non-tiled squares with side , if they exist, place the squares with side , if they exist, dividing each non-tiled square with side into equal squares. We will continue this procedure for by placing squares with side on the non-tiled squares with side , in turn dividing them into equal squares.
Finally, because the sum of areas of squares is greater than , then on some step, we will cover the square. Then increasing the th square to the square with side , we will get the tiling of the unit square with the given squares.
If some then the th square will cover the unit square. Now let's assume the case when for all .
Every number must satisfy for some integer . Now let's decrease every th square to the square with side . Then its area would decrease by at most times. Therefore the area of all squares will be greater than .
Now let's prove we can tile the unit square fully with the new squares. Let's divide the unit square into squares of side . First place the squares with side , if they exist. Then on the non-tiled squares with side , if they exist, place the squares with side , if they exist, dividing each non-tiled square with side into equal squares. We will continue this procedure for by placing squares with side on the non-tiled squares with side , in turn dividing them into equal squares.
Finally, because the sum of areas of squares is greater than , then on some step, we will cover the square. Then increasing the th square to the square with side , we will get the tiling of the unit square with the given squares.
Techniques
Constructions and lociGames / greedy algorithms