Классная задача на пример плюс оценку, раскраски и четность одновременно. Комбинирование методов решения всегда приводит к нетривиальным решениям.
Условие:
В каждой клетке полоски длины 100 стоит по фишке. Можно за один рубль поменять местами любые две соседние фишки, а также можно бесплатно поменять местами любые две фишки, между которыми стоят ровно три фишки. За какое наименьшее количество рублей можно переставить фишки в обратном порядке?
Решение:
Оценка:
Каждая фишка должна поменять четность. Бесплатная операция не меняет четность, а платная меняет четность двух фишек. Поэтому потребуется не менее 50 рублей.
Пример:
Занумеруем фишки по порядку от 0 до 99. Покрасим клетки в 4 цвета abcda..d. Бесплатная операция меняет местами фишки в соседних одноцветных клетках. Поэтому в клетках одного цвета фишки можно переставить в любом порядке. Поменяем местами фишки во всех парах bc и da - это 49 платных операций. В клетках цвета b и c уже можно расставить фишки в нужном порядке бесплатно. В клетках цвета a и d сделаем так, чтобы фишки 0 и 99 оказались рядом. Поменяем их последней платной операцией и дорасставим фишки в нужном порядке.
Всем кто дочитал, спасибо за внимание! Удачных вам вычислений!