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