Задача

Эта задача впервые была опубликована в разделе "Математические развлечения" в журнале Scientific American. Эта маленькая задача на самом деле очень трудная для решения.

Имеется 5 кружков, 3 черных и 2 белых, последовательность расположения которых чередуется через одного, как показано на этом рисунке.

А нужно эти кружки расположить так, чтобы сначала были вместе 3 черных, а затем вместе 2 белых, как показано на рисунке ниже. Причем, нужно определить, за какое минимальное количество перемещений можно перейти от расположения кружков на верхнем рисунке к расположению на нижнем рисунке.

При этом условия перемещения кружков следующие:

• За один раз можно перемещать только 2 кружка одновременно. Причем, можно перемещать только такие 2 кружка, которые соприкасаются друг с другом и имеют два разных цвета.
• При этом порядок следования цветов перемещенных кружков должен сохраниться таким же, каким был этот порядок первоначальным. И оба перемещенных кружка должны по прежнему соприкасаться друг с другом.
• Перемещать эти два кружка можно на любое свободное место на линии, в том числе и на некоторое расстояние от других кружков. Под свободным местом на линии понимается такое место, где могут поместиться, минимум, два кружка.
• В процессе таких перемещений могут образовываться разрывы в цепи кружков с пустыми местами, но, после окончания всей процедуры перемещений, никаких разрывов остаться не должно. Все 5 кружков снова должны соприкасаться друг с другом, как на картинке.
• Номера кружков (их первоначальный порядок) не имеют значения. В окончательном построении порядок следования номеров кружков может быть любым.

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

Решение задачи

Всего требуется 4 перемещения:

1. Кружки 3 и 4 перемещаем направо. Но между кружками 5 и 3 оставляем место для двух кружков.
2. Кружки 1 и 2 перемещаем направо за 4-й кружок так, чтобы между кружками с номерами 1 и 4 не оставалось пустого места.
3. Кружки 4 и 1 перемещаем в просвет для двух кружков между кружками 5 и 3. (Этот просвет образовался на первом перемещении.)
4. Кружки 5 и 4 перемещаем в просвет для двух кружков между кружками 3 и 2. (Это тот самый просвет, откуда на 4-м перемещении забрали кружки 4 и 1.)

Если не подглядывать в эту картинку, то решение этой задачи найти очень непросто.

Легкий вариант задачи

У этой задачи есть более легкий вариант. Всё то же самое, только дополнительно можно перемещать еще и два кружка одного и того же цвета.

Подсказка: Это можно сделать всего за 3 перемещения. Попробуйте найти эти три перемещения.

------------------

Автор статьи: Евгений Миронов.