ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
Задача 66819
УсловиеВ каждой клетке полоски длины 100 стоит по фишке. Можно за 1 рубль поменять местами любые две соседние фишки, а также можно бесплатно поменять местами любые две фишки, между которыми стоят ровно три фишки. За какое наименьшее количество рублей можно переставить фишки в обратном порядке?РешениеОценка. Каждая фишка должна поменять чётность своего номера. Бесплатная операция не меняет чётность, а платная меняет её у двух фишек. Поэтому потребуется хотя бы 50 рублей. Алгоритм. Занумеруем фишки по порядку числами от 0 до 99. Покрасим клетки в четыре цвета: abcdabcd...d. Бесплатная операция меняет фишки в соседних одноцветных клетках. Поэтому в клетках одного цвета фишки можно бесплатно переставить в любом порядке. Поменяем фишки во всех парах bc и da – это 49 платных операций. В клетках цвета b и c фишки уже можно расставить нужным образом бесплатно. В клетках цвета a и d сделаем так, чтобы фишки 0 и 99 встали рядом. Поменяем их последней платной операцией и дорасставим все фишки в нужном порядке. ОтветЗа 50 рублей. Замечания1. Ср. с задачей 66826. 2. 4 балла. Источники и прецеденты использования |
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|
![]() |