M. V. Murraikin

The city is a rectangular grid, with a five-story building in each cell. The renovation law allows choosing two adjacent cells (by side) with buildings and demolishing the building with fewer floors (or the same number). At the same time, the number of floors from the demolished building is added to the remaining building. What is the minimum number of buildings that can be left in the city using the renovation law, if the city has dimensions

a) $20 \times 20$ cells;

b) $50 \times 90$ cells
a) A square $20 \times 20$ can be divided into 25 squares $4 \times 4$, in each of which one house can be left. Indeed, in a $2 \times 2$ square, it is easy to gather all the houses in one cell. We will gather them in the marked cells (left image). Similarly, all the marked cells are gathered.
![](https://cdn.mathpix.com/cropped/2024_05_06_5dbee4d95f83bceb3891g-35.jpg?height=406&width=1800&top_left_y=0&top_left_x=0)

b) (Zamir Ashurbekov, Derbent) Since 4500 divided by 16 leaves a remainder of 4, it is sufficient to divide the rectangle $50 \times 90$ into 16-cell figures and one 4-cell figure, in each of which all houses can be gathered. A suitable 16-cell figure and the order of gathering houses in it are shown in the center image.

First, we will form a rectangle $8 \times 10$ from the 16-cell figures (right image).

The rectangle $50 \times 90$ will be divided into four rectangles: $50 \times 72$, $32 \times 10$, $32 \times 8$, and $18 \times 18$. The first two can be divided into rectangles $8 \times 10$, the third into squares $4 \times 4$, and the last into four rectangles $8 \times 10$ and a square $2 \times 2$ (center). This is what was required.

## Answer

a) 25 houses; b) 282 houses.

Submit a comment