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