|
|
 |
Условие
Город представляет из себя клетчатый прямоугольник, в каждой клетке стоит пятиэтажный дом. Закон о реновации позволяет выбрать две соседних по стороне клетки, в которых стоят дома, и снести тот дом, где меньше этажей (либо столько же). При этом над вторым домом надстраивается столько этажей, сколько было в снесённом доме. Какое наименьшее число домов можно оставить в городе, пользуясь законом о реновации, если город имеет размеры
а) 20×20 клеток;
б) 50×90 клеток?
Решение
а) Квадрат 20×20 разобьём на 25 квадратов 4×4, в каждом из которых можно оставить по одному дому. Действительно, в квадрате 2×2 легко собрать все дома в одной клетке. Соберём их в отмеченных клетках (рис. слева). Аналогично собираются все отмеченные клетки.
Из 16-клеточных фигур сначала сложим прямоугольник 8×10 (рис. справа).
Прямоугольник 50×90 разобьём на четыре прямоугольника: 50×72, 32×10, 32×8 и 18×18. Первые два из них разбиваются на прямоугольники 8×10, третий – на квадраты 4×4, а последний – на четыре прямоугольника 8×10 и квадрат 2×2 (в центре). Что и требовалось.
Ответ
а) 25 домов; б) 282 дома.
Замечания
1. Можно показать, что приведённая оценка точна для всех рямоугольников с чётными сторонами не меньше 8. Для прямоугольников $6×8n$ это уже не так.
2. Баллы: 5 + 5.
