Skip to main content
OlympiadHQ

Browse · MathNet

Print

XXIV 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.

Techniques

Constructions and lociGames / greedy algorithms