Задача

Эта задача впервые была опубликована в разделе "Математические развлечения" в журнале 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 перемещения. Попробуйте найти эти три перемещения.

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

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

Задача

Пять белых и пять черных шашек построены в горизонтальную линию на 11 клетках с одной свободной клеткой между ними.

Белые шашки могут ходить только направо на одну свободную клетку вперед, или могут перепрыгивать через одну черную шашку, которая стоит рядом на соседней правой клетке, если следующая клетка справа от черной шашки свободна. Аналогично, и черные шашки могут ходить только налево на одну следующую свободную клетку вперед, или могут перепрыгивать через одну белую шашку, которая стоит рядом на соседней левой клетке, если следующая клетка слева от белой шашки свободна.

Назад ходить и перепрыгивать запрещено.

Ходить можно в любом порядке. То есть не обязательно ходы белых и черных шашек должны чередоваться.

Как переместить все белые шашки направо на место черных, а черные налево на место белых?

За какое количество ходов это можно сделать?

Решение

Перестановка всех шашек требует минимум 35 перемещений.

Так как всегда только одна пустая клетка, то однозначно расписать всю запись всех ходов можно простым указанием, какая шашка перемещается, белая (б) или черная (ч).

Вот как это выглядит с картинками через каждые 7 ходов.

б, ч, ч, б, б, б, ч.

ч, ч, ч, б, б, б, б.

б, ч, ч, ч, ч, ч, б.

б, б, б, б, ч, ч, ч.

И, наконец последние 7 ходов: ч, б, б, б, ч, ч, б.

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

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

Задача про разъезд поездов

На рисунке показано, как на одноколейной железной дороге встретились два электровоза B и C с четырьмя вагонами. Между ними имеется разъезд. Но правая половина разъезда ремонтируется (показано штриховыми линиями). Поэтому проехать через разъезд невозможно.

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

Как разъехаться этим двум поездам, если к электровозам можно подцеплять и свои и чужие вагоны как спереди, так и сзади?

Решение задачи про разъезд поездов

Решение показано на рисунке ниже:

1. Электровоз C сдает назад, чтобы между ним и разъездом полностью поместился электровоз B со всеми 4-мя вагонами. После чего электровоз B сдает назад так, чтобы его 2 последних вагона зашли на разъезд. Эти 2 последних вагона отцепляются и остаются там. А электровоз B со своими первыми двумя вагонами по главному пути сдает назад так, чтобы оказаться снова справа от разъезда. (См. этап 2.)
2. Электровоз C заезжает на разъезд, прицепляет к себе оставленные на разъезде вагоны и возвращается с ними налево к своим вагонам. При этом он освобождает место для электровоза B с двумя вагонами. Электровоз B со своими двумя вагонами по главному пути заезжает налево от разъезда и, затем, сдает назад так, чтобы въехать со своими вагонами на левую часть разъезда. (См. этап 3.)
3. Электровоз C по главному пути перегоняет направо два вагона из состава B и все свои 4 вагона. Электровоз B перегоняет прицепленные к нему два вагона с переезда на главный путь налево. При этом он уходит подальше налево, освобождая место для возвращения обратно состава C. (См. этап 4.)
4. На освободившееся слева от переезда место возвращается сначала весь состав C, а затем электровоз C перегоняет туда и оставшиеся последние два вагона состава B. Потом электровоз C сдает с этими вагонами назад так, чтобы загнать эти два вагона состава B на левую часть переезда и оставляет из там. (См. этап 5.)
5. Электровоз C прицепляет к себе все свои 4 вагона и по главному пути уезжает направо. Электровоз B со своими двумя вагонами сдает назад так, чтобы прицепить к составу оставшиеся на переезде два вагона, и после этого окончательно уезжает налево. (См. этап 6.)

Всё, составы разъехались!

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

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