ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66819
Темы:    [ Вспомогательная раскраска (прочее) ]
[ Четность и нечетность ]
Сложность: 3
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

В каждой клетке полоски длины 100 стоит по фишке. Можно за 1 рубль поменять местами любые две соседние фишки, а также можно бесплатно поменять местами любые две фишки, между которыми стоят ровно три фишки. За какое наименьшее количество рублей можно переставить фишки в обратном порядке?

Решение

Оценка. Каждая фишка должна поменять чётность своего номера. Бесплатная операция не меняет чётность, а платная меняет её у двух фишек. Поэтому потребуется хотя бы 50 рублей.

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

Ответ

За 50 рублей.

Источники и прецеденты использования

олимпиада
Название Турнир городов
номер/год
Номер 41
Год 2019/20
вариант
Вариант осенний тур, базовый вариант, 8-9 класс
задача
Номер 3

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .