Задача "Две ромашки"

Материалы для занятия в математическом кружке, в летней школе.

Впервые эта задача появилась в журнале "Математика в школе" №6 за 2007 год в разделе "Задачи" под номером 4958.

Десять пронумерованных круглых фишек расположены так, что образуют две пересекающиеся "шестилепестковые ромашки" с центральными фишками 5 и 6. Каждую "ромашку" можно повернуть на угол кратный 60° вокруг центральной фишки. Можно ли, совершив несколько таких поворотов, поменять местами фишки 5 и 6, а все остальные фишки не изменили бы своего расположения.

Решение. Можно. В самом деле, нетрудно поменять местами фишки 5 и 6, не обращая при этом внимания на остальные. Для этого нужно выполнить всего три поворота "ромашек" по часовой стрелке на угол 60° в такой последовательности: левая, правая, левая. Проделаем это:

Сравнивая начальное и конечное расположение фишек, проследим, какое перемещение совершила каждая фишка. Перемещение каждой фишки обозначим стрелкой. Получим следующую схему.

Заметим, что фишки циклически перемещаются в трёх изолированных группах, содержащих 2, 3 и 5 фишек. Эти числа взаимно просты, поэтому, если последовательно выполнить 15 раз (кратное 3 и 5) повороты "ромашек" левая, правая, левая, то циклы из 3 и 5 фишек завершатся, то есть, фишки этих циклов вновь займут исходное положение. При этом цикл из двух фишек, а это фишки 5 и 6, останется незавершенным, то есть фишки 5 и 6 поменяются местами.

История этой задачи

Родом эта задача из головоломок. Когда-то я придумал механическую головоломку "19", внешний вид которой показан на рисунке.

На рисунках ниже показано внутренне устройство головоломки. Дно круглой коробки с асимметричной круглой прорезью может вращаться с помощью ручки, расположенной снизу. На ручке укреплен диск с шестью штырями, посредством которых через прорезь в дне коробке осуществляется доступ к 19 фишкам, расположенным внутри коробки в форме правильного шестиугольника. Его периметр обрамлен шестью рейками, между каждой из которых и бортом коробки вложены упругие поролоновые вкладыши. Сверху вся конструкция прикрыта стеклом.

19 круглых пронумерованных фишек группами по шесть с помощью диска со штырями могут вращаться по круговым орбитам, другими словами головоломка "шесть ромашек". На схеме цветом отмечены центральные фишки этих "ромашек". Понятно, что, наводя порядок в расположении фишек этой головоломки, на заключительном этапе придется искать алгоритм решения головоломки "две ромашки". Она на схеме выделена голубым цветом.

Исследуя коммутаторы, я обнаружил удивительную операцию , которая меняет местами две соседние фишки, оставляя на своих местах все остальные. Здесь буквой Л обозначена левая "ромашка", буквой П - правая. Стрелки указывают направление вращения. Эту операцию нетрудно скорректировать так, чтобы она меняла местами фишки Л и П. Неожиданным для меня оказалось существование такой операции, потому что я помнил трюк С. Лойда с миллионной премией в его знаменитой головоломке "15".

Вскоре головоломка "19" появилась с другим механизмом перемещения фишек, основанном на силе тяжести фишек. Автор новой версии головоломки П. Манташьян из Черкесска назвал её "Цветной капустой". После появления новой версии головоломки с более простым механизмом интерес к ней у меня постепенно угас.

Алгоритм решения головоломки пролежал в моих бумагах почти 20 лет. Я вспомнил о нем, когда в журнале "Квант" №4 за 2005 год появилась задача И. Игнатовича: Цифры 1, 2, 3, 4, 5, 6 расположены на двух окружностях так, как показано на рисунке. За один ход можно сдвинуть стоящие на одной окружности четыре цифры по кругу так, чтобы каждая из них заняла место соседней с ней цифры. Можно ли за несколько ходов добиться того, чтобы цифры 1 и 6 поменялись местами, а все остальные цифры оказались на первоначальных местах?

Приведу её решение, опубликованное в журнале "Квант" №1-06. Этого сделать нельзя. Занумеруем грани кубика цифрами от 1 до 6 так: верхняя - 1, нижняя - 6, левая - 5, правая - 3, передняя - 2, задняя - 4. Тогда циклические перестановки четырех цифр окружности соответствуют поворотам кубика на 90^o, но сколько ни вращай кубик - не получишь новый кубик, где грани 1 и 6 переставлены, а все остальные грани остались на своих прежних местах.

Меня вдохновляло то, что похожие по условию эти две задачи на удивление давали противоположные результаты. В задаче И. Игнатовича фишки нельзя поменять местами, а в моей задаче - можно. Недостатком моих "двух ромашек" являлось не "школьное" решение, основанное на коммутаторах. Вернувшись к этой задаче вновь, мне удалось найти решение, доступное школьникам. Именно оно приведено в журнале "Математика в школе".

"Обкатав" эту задачу на своих учениках, я понял, что это действительно хорошая олимпиадная задача, потому что первое, что приходит в голову при решении задачи, это найти инвариант и дать отрицательный ответ. Вскоре я отослал её Н.Х. Агаханову, в методическую комиссию Всероссийской олимпиады, но на олимпиаде задача не появилась, наверное, не приглянулась членам комиссии. А вот редактору отдела "Задачи" журнала "Математика в школе" С.И. Токареву она понравилась и вскоре появилась на страницах журнала в отделе Задачи" под №4958.

Задача вызвала живой интерес у читателей. Это видно из обзора решений. Любопытные читатели обнаружили прямую связь задачи с головоломкой "Ротос", выпускавшейся в ГДР в 1980-е гг.

Более того, решатели стали негласно соревноваться в поиске самого короткого решения, хотя этого совершенно не требовало условие задачи. Интересно было бы познакомиться с 21-ходовым решением В.Л. Дорофеева.

Но больше всего меня поразило 17-ходовое решение, которое прислал А.Ю. Эвнин, доцент ЮУрГУ из Челябинска. Вот оно: . Оказывается, это решение нашёл с помощью компьютерной программы его коллега (и бывший ученик) Андрей Демидов. Он же обнаружил, что от любой конфигурации можно перейти к любой другой не более чем за 19 ходов.

Мне известно, что С.И. Токарев предлагал задачу "Две ромашки" на заключительном этапе конкурса имени А.П. Савина 2007 года, который проводится под эгидой журнала "Квант", но отчетными материалами этого соревнования школьников я не располагаю.

Региональная олимпиада Информатика-2008 ЮУрГУ

Совсем недавно А.К. Демидов из Челябинска прислал мне письмо, в котором сообщил, что в Южно-Уральский Государственный университет (ЮУрГУ) ежегодно проводит региональную олимпиаду по информатике. В олимпиаде участвуют учащиеся и выпускники средних школ, гимназий и лицеев их региона. 20 апреля 2008 года состоялся очный тур, на котором участникам предлагалось решить пять задач. Вот выдержка из его письма: "Я думаю, что Вам, как автору задачи "Две ромашки" из журнала "Математика в школе" №6 за 2007 год, будет интересно узнать, что четвертой задачей очного тура нашей олимпиады была задача D "Головоломка". Это вариант Вашей задачи, переформулированный специально для юных программистов.

Высылаю также текст, решение на Pascal и тесты для задачи. Как оказалось, школьники на соревнованиях использовали рекурсивный перебор, с помощью которого можно решить головоломку, если число ходов не превышает 12 (т.е. перебирали 4^12 вариантов). Правильный же способ заключается в создании графа состояний из 10! (=3628800) вершин и поиск в ширину по нему. Для ускорения работы в solve.pas используется специальный массив index, позволяющий быстро получить по перестановке ее номер.

Программа analiz.cpp (analiz.exe) позволяет доказать, что для достижения любого состояния из начального требуется не более 19 ходов, и выводит для каждого количества ходов от 1 до 19 пример перестановки, которая достигается только за это число ходов.

С уважением, Демидов А.К. ЮУрГУ

Нижеследующий скрин с текстом задачи и результаты региональной олимпиады в Челябинске я взял на сайте http://ipc.susu.ac.ru/4794-4.html )

Результаты олимпиады Информатика-2008

В олимпиаде приняло участие 41 ученик. Ниже в таблице приведены результаты первых шести участников. В желтом столбце D приведены по 100-балльной шкале оценки за решение задачи "Головоломка". Нетрудно заметить, что для участников олимпиады она оказалась самой трудной задачей, и вообще, полностью с нею не справился ни один участник.

Головоломка в Интернете

Совсем недавно, путешествуя по Интернету, я обратил внимание на логическую игру "Круговорот". К моему удивлению, это оказался компьютерный вариант моей головоломки "19", разработанный по заказу компании "Яндекс" агентством "Брэйн Шторм". Интерфейс её изображен на рисунке.

 

Слева изображено игровое поле с разноцветными фишками, в запутанном виде, справа образец, по которому нужно восстановить узор. Задача играющего - передвинуть фишки так, чтобы в итоге восстановить узор мозаики, руководствуясь девизом "Кручу-верчу, распутать хочу".

Если нажать на любую из семи центральных фишек, то прилегающие к ней шесть фишек переместятся по окружности на угол 60^о против часовой стрелки. Это считается одним ходом.

В "Круговороте" 15 уровней сложности, от первого - самого простого, до последнего - самого трудного (я бы сделал 19 уровней). В каждом уровне для восстановления мозаики играющему отводится 50 ходов. Если узор восстановлен за меньшее ходов, то все оставшиеся до 50 ходы превращаются в призовые очки.

Здесь же установлены счетчики очков и ходов, кнопки управления звуком, повторного прохождения уровня и перезапуска игры.

На рисунке показано расположение фишек в 8-ом уровне. Этот пестрый хаос из фишек пяти цветов нужно упорядочить и сложить красивую мозаику. Результат задачи "Две ромашки" позволяет утверждать, что любые две фишки можно поменять местами, поэтому любая мозаика обязательно сложится. Нужно только уложиться в 50 ходов, иначе не получишь призовые очки в свою копилку.

Приятная игрушка, хорошо развивающая логическое мышление, в которой реализуется один из главных принципов обучения: от простого к сложному. Рекомендую найти её по адресу http://play.yandex.ru/load.xml?game_id=72, поиграть и получить удовольствие. Лично я получил от этого громадное удовольствие. Спасибо разработчикам компьютерного варианта задачи.

Ещё нужно добавить, что полное исследование головоломки "19" пока находится за пределами возможностей вычислительной техники, потому что число её различный состояний равно 19!10¹⁷. К примеру, у кубика Рубика число состояний примерно такое же 4,3x10¹⁸, и минимальное число ходов было найдено отбрасыванием из рассмотрения большинства вариантов, но все равно потребовало 63 часа работы суперкомпьютера.

Вот такая история этой задачи. Я надеюсь, что на этом она не закончится. Думаю, что она скоро появится в сборниках задач, для подготовки учащихся к различным математическим соревнованиям. В математических журналах уже появились задачи-родственники, над которыми я предлагаю поразмышлять.

Упражнения для самостоятельной работы

(Журнал "Квант, №6, 2009 г.) Из пронумерованных квадратных фишек 1x1 сложена фигура, содержащая два квадрата 2x2, причем фишка с номером 4 - общая. Фишки каждого квадрата 2x2 можно повернуть вокруг его центра на угол кратный 90^о.

а). Можно ли при помощи таких поворотов получить расположение, показанное на рисунке в центре.

б) Можно ли при помощи таких поворотов получить расположение, показанное на рисунке справа.

(Автор Авилов Н.И)

(Журнал "Математика в школе, №10, 2009 г.) Головоломка "6" состоит из двух пересекающихся колец и 6 пронумерованных шариков. Каждое кольцо содержит 4 шарика, расположенных в вершинах квадрата рис.1). Разрешается выбрать любое кольцо и повернуть его (вместе с шариками) на 90^о. (На рис. 2 показано расположение шариков, получающееся из начального поворотом правого кольца на 90^о по часовой стрелке.) Можно ли при помощи разрешенных операций получить расположение, показанное на рис. 3?

Авторы И.Ф. Акулич, К.Э. Каибханов, С.И.Токарев

Квадрат 3x3 сложен из квадратных фишек 1x1. Фишки пронумерованы в каждом ряду слева направо. Фишки каждого квадрата 2x2 можно повернуть вокруг его центра на угол кратный 90^о. При помощи нескольких таких поворотов получите расположение, в котором фишки пронумерованы "змейкой".

(Автор Авилов Н.И)