Олимпиадная задача про перекрашивание полоски 1×99 — инварианты
Задача
Имеется полоска 1×99, разбитая на 99 клеток 1×1, которые раскрашены через одну в чёрный и белый цвет. Разрешается перекрашивать одновременно все клетки любого клетчатого прямоугольника 1×k. За какое наименьшее число перекрашиваний можно сделать всю полоску одноцветной?
Решение
Оценка. Назовём перемычкой отрезок, разделяющий две клетки разных цветов. В начале у нас имеется 98 перемычек. Каждое перекрашивание изменяет число перемычек не более чем на 2. Значит, 48 перекрашиваний не хватит.
Алгоритм. Перекрасим все клетки со второй по 98-ю, затем все клетки с третьей по 97-ю, ..., наконец, одну 50-ю клетку. После этого полоска станет одноцветной.
Ответ
За 49 перекрашиваний.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет