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